Problem fixed!
I received this email from RIM support this morning:
"This issue was caused by conflicting service books being present on the Blackberry. We have had the WLM 2.1 provisioning removed and customers should no longer receive the WLM 2.1 [BBIMConfig] service book. This issue affected the 8800, 8820 and 8320 models. Please remove service book WLM 2.1 [BBIMConfig] on the Blackberry. Go to options > advance options > service books and delete WLM 2.1 [BBIMConfig]."
I did the following and can now log into Windows Live Messenger.
Hope it works for you too.