Vocês acessam como? Porque só dá certo se usarem aquele login que o facebook fornece. Por exemplo. cajaboy@facebook.com.br e a senha.
O login utilizado pelo Facebook é [ID]@chat.facebook.com
Eu sempre utilizei ele no Empathy, nunca tive problemas. A primeira vez ele não conectou e o Facebook me notificou algo tipo "Alguém está tentando utilizar sua conta." e eu dei Ok dizendo que era eu e não tive mais problemas.
Conecto sem problemas no Empathy, Pidgin, Psi, Miranda...