I'm having a similar problem, but maybe it's slightly more bizarre.
I upgraded OS X to 10.4.8 last night and updated Messenger to version 6 as well. Now I can't log in to the service.
I thought maybe it was version 6, so I trashed that, downloaded 5.1 and installed that again. No dice. It sort of logs in - it gets to the window but it doesn't open my buddy list.
I downloaded Adium and got the same result. Not able to log in.
I have a spare Mac lying around - an old Powerbook. I had version 4 on there. So I logged in, and I got the same no-buddy-list error as with 5.1.
I am able to log in using Live Messenger on PC. My fiancee is also able to log in on version 4 on the old Powerbook.
Anyone have any ideas how I can fix this?