Похоже, что gnome-terminal этого не поддерживает (по крайней мере встроенным способом). Советовали же использовать konsole или xterm. Первого у меня нет (KDE-шный), а второй запускается, например, так:
xterm -en cp1251
Создаем ярлык, туда эту команду и - вперед.