Fix stubborn 'Setting locale failed.'

You could also try to install the locales-all package, to avoid having to generate any locales ever again.

Had the same problem and found the solution. You have to recreate the custom.UTF-8 locale def (the "custom" file is probably there because you changed the date or time format). Run

sudo localedef -f UTF-8 -i custom custom.UTF-8

Another way to do this is to add the locale to the ones you want dpkg-reconfigure locales to configure for you. On Debian:

echo 'custom.UTF-8 UTF-8' |sudo tee -a /etc/locale.gen
sudo dpkg-reconfigure locales

On Ubuntu:

echo 'custom.UTF-8 UTF-8' |sudo tee -a /var/lib/locales/supported.d/local
sudo dpkg-reconfigure locales

Hope this helps!