Supondo que você já tenha feito o backup de qualquer banco de dados 9.4, um "purge" em vez do "remove" teria se livrado do arquivo /etc/postgresql/9.4/main/postgresql.conf com o "port = 5432" linha. Como ainda existia quando você fez a instalação do 9.5, a instalação usou a próxima porta, 5433. Geralmente, isso é feito para permitir que uma versão posterior do postgresql seja instalada e registrada antes de excluir a versão antiga.
Você pode editar a porta do arquivo /etc/postgresql/9.5/main/postgresql.conf para ser 5432 e refazer a limpeza do apt-get postgresql-9.4 para limpar os arquivos de configuração antigos.
Você pode rastrear os arquivos restantes de 9,4 com o locate
locate postgresql/9.4
e remova-os manualmente para evitar que o sistema tente iniciar o serviço não mais presente.