initdb will absorb locale/encoding from its environment, unless told otherwise through a --locale switch. So the usual expectation would be that it'd work like you want. Perhaps the Ubuntu packager set LANG=C in the postgres user's ~/.profile, or some such? Poke around a bit in the package's files, it shouldn't be too hard to find where the damage is being done.
