Спасибо.
Вот нашол как:
Запускаем gconf-editor, он ещё называется как "Редактор конфигурации" .
Дальше по дереву:
/apps/gedit-2/preferences/encodings
Правой кнопкой мыши кликаем по ключу auto_detected, выбираем пункт "Изменить ключ".
Видим пукнт "WINDOWS-1251", нажав несколько раз на кнопку "Вверх" перемещаем его выше так, чтобы сверху была только utf-8.
Жмём "ОК". Закрываем gconf-editor. Теперь gedit будет спокойно открывать файлы и в cp-1251.
В моём случае надо было создать ключ WINDOWS-1251.