O pacote postgresql
é apenas um pequeno pacote de transição que possui um conjunto Depend no pacote real.
postgresql-8.4
é o pacote real, isso é instalado? (deve ser, desde que o que você instalou depende disso).
Além disso, parece que o postgresql simplesmente não possui um script init.d. Experimente:
service postgresql start