I had this problem too, I tried this in the help section of Windows live messenger and it seemed to work.. Good Luck
Delete your Contacts cache folder
If your contact list is empty or incomplete after you upgrade to Windows Live Messenger, the cached contact list may not have updated correctly. Before you can delete your Contacts cache folder, make sure you can view your complete folder list in Windows Explorer.
View your complete folder list
On the taskbar, right-click Start, and then select Explore.
Click on Tools, and then select Folder Options.
In the Folder Options window, click the View tab.
In the Advanced Settings list, select Show hidden files and folders, make sure Hide extensions for known file types is not selected, and then click OK.
In the Windows Explorer window, click View, select Explorer Bar, and then verify that Folders is checked.
Delete your Contacts cache folder
After changing your Windows Explorer settings:
On the taskbar, right-click Start, and then select Explore.
In the folder list on the left-hand pane, navigate to the folder C:\Documents and Settings\Your Windows logon name\Contacts\Your Messenger email address.
Delete all of the files within the folder Your Messenger email address.
In the folder list on the left-hand pane, navigate to the folder C:\Documents and Settings\Your Windows logon name\Local Settings\Application Data\Microsoft\Windows Live Contacts\Your Messenger email address.
In the Your Messenger email address folder, delete the real and shadow folders.
Close Windows Explorer and try to sign in to Messenger again
