Странная проблема локали на сервере Ubuntu

Установлен новый Ubuntu 13.10 64 бит на сервере Hetzner. Сразу после установки попытался выполнить apt-get update и apt-get dist-upgrade. Получение следующей ошибки почти во всех операциях apt-get

perl: warning: Setting locale failed.
perl: warning: Please check that your locale settings:
    LANGUAGE = "en_US:en",
    LC_ALL = (unset),
    LC_CTYPE = "UTF-8",
    LANG = "en_US.UTF-8"
    are supported and installed on your system.
perl: warning: Falling back to the standard locale ("C").
locale: Cannot set LC_CTYPE to default locale: No such file or directory
locale: Cannot set LC_ALL to default locale: No such file or directory

Много гуглил и пробовал множество решений. Нет успеха Все те же предупреждения. Очень раздражает и не знаю, что стоит за этим.