Gnome terminal doesn't like to obey the "normal" locale file.  It uses "/etc/X11/gdm/locale.alias", and therefore usually has the incorrect character encoding.  eg.

instead of:

The way to solve this is to create a symlink to the correct locale.

1) Backup the original file:

mv /etc/X11/gdm/locale.alias /etc/X11/gdm/locale.alias.bak

2) Create the symlink:

ln -s /etc/locale.gen /etc/X11/gdm/locale.alias

It's also worth noting that I only have the following in my file:

en_GB ISO-8859-1
en_GB.UTF-8 UTF-8