On Ubuntu Hardy Heron (8.04), these instructions didn't work and instead I followed the pointers in here: http://articles.slicehost.com/2008/4/25/ubuntu-hardy-setup-page-2

sudo locale-gen en_GB.UTF-8
...
sudo /usr/sbin/update-locale LANG=en_GB.UTF-8