O pacote telepathy-gabble 0.18.1 no Ubuntu, na verdade, continha uma solução para o problema, não uma solução adequada. Citando o ChangeLog :
telepathy-gabble (0.18.1-1) unstable; urgency=low * New upstream stable release - work around Facebook server behaviour change so we don't consider its service discovery response to be spoofed (Closes: #721883) -- Simon McVittie Mon, 09 Sep 2013 13:05:13 +0100
Aparentemente, essa solução não funciona e, de fato, o status do bug foi revertido de Fix Liberado para Confirmado .
Para a correção correta, lamento que você tenha que esperar que o bug do upstream seja fixo (a menos que alguém proponha uma outra solução alternativa nesse meio tempo).