I'll bullet point things of note:

• Other accounts work on the same machine.
• This is a problem across a few machines.
• I can sign in no problem on some machines.
• I can use Web Messenger on the problem machines.
• I'm using the latest version of Messenger.
• I've uninstalled, rebooted, reinstalled, rebooted.
• Deleting the "Windows Live Contacts" folder doesn't help.
• Deleting the Contacts registry entries doesn't work.
• I'm not using AVG (and besides, can sign in with other accounts)
• It successfully connects (and signs me out of eBuddy) before erroring.
• It creates files in the Windows Live Contacts folder.
• Windows XP running on the problem machines.

I'm not sure what other things it could be...

This has also been asked at http://www.experts-exchange.com/Software/Internet_Email/Chat_-_IM/Q_25449997.html, so let's see which system gets me the better response...