estas usando el Windows Live Messenger? A veces da problemas, puede llegarte a decir que no tienes ni un contacto agregado...
Mira tambien que ahora en vez de salirte por el nombre, te salga por la direccion de correo, que puede ser tambien. De todos modos puedes volver a agregarle de nuevo, ya que al estar aceptado de antes en su MSN no tendras que esperar que te admita de nuevo.