Como já mencionado, este é um erro de empatia (ou pelo menos com alguns dos protocolos de conexão usados na empatia).
Existe uma solução alternativa para o protocolo MSN:
O Empathy pode usar os mesmos protocolos de conexão que o pidgin usa (libpurple) através do telepathy-haze, que é instalado por padrão.
Para o MSN funcionar, desinstale o telepathy-butterfly:
sudo apt-get remove telepathy-butterfly
Em seguida, reinicie o Empathy, que agora voltará a usar o telepathy-haze para conexões do MSN. Agora você deve poder definir "use o método http" em "Editar -> Contas" depois de adicionar uma nova conta para o MSN.
Pode haver soluções alternativas para outros protocolos. Para mim, tudo o resto funciona imediatamente (pelo menos por trás do proxy no trabalho).