Acabei de descobrir uma resposta para algo que estava me incomodando: o Empathy não conectava na rede do Facebook. Fiquei procurando a resposta por um bom tempo, até encontrar este [1] bug. Era exatamente o meu problema; tudo estava bem configurado no Empathy, mas havia um erro de autenticação.
Entretanto, um dos comentários dava a resposta para o problema: fazer login no Facebook. Eu costumava fazer login no Facebook usando o meu email e não o meu usuário do Facebook. Daí, quando tento autenticar via Empathy, dá erro. A solução é simplesmente fazer logout no Facebook e fazer o login usando seu usuário [2] no Facebook. Depois disso, tudo funciona como deveria.
Logo, o problema deve ser com a autenticação do Facebook e não com o Empathy em si.
Atualização: sobre onde fazer seu usuário do Facebook.
Vá para a configuração da sua conta (Account Settings) e lá você deverá ver algo como Usuário ou Username. É lá que você estabelece seu usuário do Facebook.
[1] - https://bugs.launchpad.net/ubuntu/+source/empathy/+bug/542477
[2] - Ex.: se http://www.facebook.com/alexandre for a sua página, 'alexandre' é o seu usuário ;)