I know this issue is quite old, but I just stumbled over the same Problem.
Just having a closer look on the output of
apt-get install postgresql I noticed the output first states that something is wrong with my locale settings and in the end reports, the cluster could not be created:
Error: The locale requested by the environment is invalid.
Error: could not create default cluster. Please create it manually with
pg_createcluster 9.1 main --start
or a similar command (see 'man pg_createcluster').
To finally solve the issue it helps to (re-)install the locales and reset the locale configuration. For me (using a debian 7.8 system) this was done by:
apt-get install locales
if it was installed, yet.
Finally reinstall the whole postgresql server system. For me this was
apt-get --purge remove postgresql postgresql-9.1 postgresql-common
apt-get install postgresql postgresql-9.1 postgresql-common
I hope this will help someone in the future to figure it out faster than I did :-)