The only reason I use Microsoft's IM app as opposed to any other is because WLM is the dominant IM software in my country. I'd say there are maybe 1000 people using ICQ and 2 million using WLM (as an example).
Umm, I digress
Lookwise, there is a lot that needs to be done. Messenger has looked worse and worse with every version since 8.1, and v2009 looks like, dare I say it, complete shit. Not that I'd give a hoot normally, but since I can't even log on to the network without updating to v14, it suddenly becomes personal. It looks so bad in fact, that it got me in a bad mood this morning, which still sort of lingers in my mind.
Windows Messenger needs to look like MSN MESSENGER. Circa 7.5-8.0. That, or the second best alternative: less bloat, more customisation options. In essence, that would pretty much entail everything that's been said in this thread already.
In sum: Less colours, less Aero Glass crap, less "features".