supongo que lo habras hecho, pero ¿has comprobado que esta activado la sincronizacion de tu cuenta live, de la agenda y contactos? en configuracion / aplicaciones / contactos, y dentro de ese menu, pulsar en "filtrar mi lista de contactos" y comprobar que este activado la cuenta live.
luego para comprobar si esta activado la sincronizacion con la agenda, entras en la agenda pulsas en "..." /configuracion y comprobar que esta activado la sincronizacion con la cuenta en cuestion.
Si eso lo tienes, pues ya es problema del telefono, y tendrias que pasar por restablecerlo de fabrica. Puede que se pueda hacer una copia de seguridad en zune, pero eso ya no lo se seguro.