Проблема при создании grub.cfg

В моем случае ничего не было предложено (Ubuntu Server 12.04LTS). Что, в конечном итоге, помогло помещать в файл /etc/environment:

LC_ALL=en_US.UTF-8
LANG=en_US.UTF-8

По какой-то причине он отсутствовал. Выходы для локали и других команд выглядели так, как будто они были правильно определены. Другими словами, не считайте само собой разумеющимся, все основные вещи объявляются там, где они должны быть объявлены.