PostgreSQL won't set up correctly

Question

I just got a new VPS running Ubuntu 14.04 which I want to use as PostgreSQL server.

I followed this guide but for some reason it won't work as described: https://www.digitalocean.com/community/tutorials/how-to-install-and-use-postgresql-on-ubuntu-14-04

So I installed PGSQL using

sudo apt-get update
sudo apt-get install postgresql postgresql-contrib

It seems like everything was installed but the initial setup failed because the server does not run. If I try to start the server it says

$ service postgresql start
* No PostgreSQL clusters exist; see "man pg_createcluster"

I googled the problem and found this in the guides comments:

I solved it, you need to set the locale before you install postgres otherwise it won't create the cluster for you, if you pay attention to the error messages at the install you can figure it out.

Adding that info to the tutorial would be great.

So I tried to uninstall the mess using:

sudo apt-get --purge remove postgresql postgresql-contrib
sudo locale-gen enUS.UTF-8
sudo apt-get install postgresql postgresql-contrib

But its still the same issue. Also it feels like the second installation after I uninstalled it was way shorter than the first installation, why does this happen?

Do I have to reinstall Ubuntu to get it work or are there other ways to get this fixed?