LC_ALL: cannot change locale

Use:

export LC_ALL=C

and install what is needed via aptitude (locales package or something equivalent).

If you still get some error due to previous failure, first run:

apt-get install -f

I was using German VPS and couldn't change locale because there was no English language pack installed.

After installing I could finally change locale

aptitude install language-pack-en