Prueba de mirar tu NAT, a lo mejor la tienes en "moderada" cuando tendria que estar en "disponible". Puede causar problemas en charlas privadas y en videoconferencias. Para pasarla a disponible tienes que abrir los puertos en tu router, a saber:
3074 tcp
3074 udp
88 udp (confirmalo que ahora no lo tengo claro)
Lo del messenger, has comprovado que tu consola tambien lo haya iniciado. Vete a la pestaña donde salen tus amigos y pulsa "Y", te iniciará tu cuenta de Messenger y deberias ver a tus contactos.
Si ya habias probado esto, lo siento pero nose que puede ser.