I found that a mixture of these cleared up this problem for me...
apt-get install locales localeconf
Select locales to be generated.
[*] en_GB ISO-8859-1[*] en_GB.ISO-8859-15 ISO-8859-15[*] en_GB.UTF-8 UTF-8
Which locale should be the default in the system environment?<-- en_GB
Manage locale configuration files with debconf? <-- Yes
If you do not wish to use the default system locale… <-- Ok
Environment settings that should override the default locale: <-- Blank
Replace existing locale configuration files? <-- Yes
If you are not sure … always supported. <-- Ok
Default system locale: <-- en_GB.UTF-8 UTF-8
Obviously you will have to choose your own countries locales, but installing the locales and localeconf is the way the way to go.