Obrigado Chida pela sua dica!
A saída foi:
sudo -u postgres cat /etc/postgresql-common/root.crt
This is a dummy root certificate file for PostgreSQL. To enable client side
authentication, add some certificates to it. Client certificates must be signed
with any certificate in this file to be accepted.
A reasonable choice is to just symlink this file to
/etc/ssl/certs/ssl-cert-snakeoil.pem; in this case, client certificates need to
be signed by the postgresql server certificate, which might be desirable in
many cases. See
file:///usr/share/doc/postgresql-doc-8.3/html/ssl-tcp.html
for details (in package postgresql-doc-8.3).
Então eu apontei root.crt no diretório de dados para /etc/ssl/certs/ssl-cert-snakeoil.pem:
ln -s /etc/ssl/certs/ssl-cert-snakeoil.pem root.crt
E então postgresql começou sem nenhum erro!