Trouble running PostgreSQL server / Server must be started under certain locale.

I'm in the process of getting Subversion and Trac running on my development
machine. So far, the installation process has gone fairly smoothly, until I
had to install the Subversion bindings for Python. Because I run Ubuntu,
and Ubuntu did not have the latest bindings in its repositories, I had to
get it from the Debian archives instead. Well, after doing this, the
PostgreSQL server is now refusing to start.

The following error message is given:
neppyman(at)loki:~$ sudo /etc/init.d/postgresql-8.1 start
* Starting PostgreSQL 8.1 database server
* Error: The server must be started under the locale en_US.UTF-8 which does
not exist any more.

Checking my locales tels me...

neppyman(at)loki:~$ locale -a
(snip)
en_US.utf8

Obviously there's a mismatch there, but I'm still learning Linux, so I don't
really know how to fix it. I've tried uninstalling and reinstalling the
locales package, but that didn't help.

Any help would be appreciated; I have quite a bit of data in my 8.1 cluster
(active phpBB, etc.), and while I could upgrade to 8.2 or even the 8.3 beta,
I don't know how I would be able to migrate a database if the postmaster
process is unable to start.

-- Geoff