Locale / Encoding mismatch

I have just attempted to upgrade to 8.3.1 and I now get this error when
trying to create a UTF8 DB:

postgres@mrnaz:~$ createdb twerl -E utf8
createdb: database creation failed: ERROR:  encoding UTF8 does not match
server's locale en_AU
DETAIL:  The server's LC_CTYPE setting requires encoding LATIN1.

I have never bothered with the server's locale, all the locale handling
in the app gets handled within the DB itself. I guess I now have to dig
into the murky world of system locales and how they affect my app
ecosystem. I don't suppose there is an easy solution to this and a short
explanation of why it now occurs is there?