Tenho certeza de que há uma resposta melhor do que isso. Mas eu tive o mesmo erro no meu ambiente de desenvolvimento, corri
sudo apt-get purge postgresql-9.1
e reconstruiu tudo em 9.3 sem problemas. Mas eu só tinha um casal usuários e bancos de dados de pequeno porte com scripts de migrações, então você não pode querer ir por esse caminho.