I’ve seen this perl error for a while and ignored it but it was stopping postgres from starting. This is on Ubuntu Intrepid 8.10, specifically a JeOS install made by vm-builder, which is the key.

$ sudo /etc/init.d/postgresql-8.3 start
 * Starting PostgreSQL 8.3 database server
 * perl: warning: Setting locale failed.
perl: warning: Please check that your locale settings:
	LANGUAGE = (unset),
	LC_ALL = (unset),
	LANG = "en_US.UTF-8"
    are supported and installed on your system.
perl: warning: Falling back to the standard locale ("C").
The PostgreSQL server failed to start. Please check the log output:
FATAL:  invalid value for parameter "lc_messages": "en_US.UTF-8"

The solution:

sudo apt-get install language-pack-en