Microsoft likes to change the encryption on their msn messanger network to be a pita from time to time
I had this issue, but its been like a year, so i dont remember the details.
if you search around, you will find that you need to download some libraries and hack it a bit to get it to work... i seem to remember needing ssl libs. a google serch should point you in the right direction
Redhat putting things in places game didnt expect was part of the problem.
When you do get it working, you will need to put in your full email address, not just the first part of it. msn allows email addresses from many domains to be used, so if you didnt use the full address as your login, they woudnt know if you were
joe@asdf.com or
joe@ms.com
Before you do anything, go to gaims website, at
http://gaim.sourceforge.net/ and get the latest version, by now they might have made it work without quite as much hacking.
Installing it on slackware is much easier, it just worked, or I could put togeather a step by step for you :/