Ubuntu 9.10 installs PostgreSQL with a default encoding of SQL_ASCII. This is dumb: SQL_ASCII basically means "I don’t care about the encoding of my data; just store garbage."
This is especially annoying since PostgreSQL will actually prevent you from creating new databases with a different encoding: if you try, you’ll be told that the "new encoding (UTF8) is incompatible with the encoding of the template database (SQL_ASCII)."
My fix was to just blow away the default cluster and re-create it with a UTF8 encoding. It should go without saying that you shouldn’t do this on a server with data you’d actually like to keep, but on a new server this works fine:
pg_dropcluster --stop 8.4 main pg_createcluster --start -e UTF-8 8.4 main
If someone knows of an easier way — one that doesn’t require destroying data — I’d love to know about it.