Uninstall of Office Communicator broke Windows Messenger

I'm on Windows XP Pro SP1 and was previously using Windows Messenger
5.1 without any problems. I recently installed Office Communicator
2007 for work and used it for a day. Then I decided that Office
Communicator web access provided enough of the functionality I needed
so I uninstalled Communicator.

After the uninstall, Windows Messenger no longer worked. I tried
downloading and reinstalling the Windows Messenger 5.1 client, but no
luck. It installs without errors but both the Start Menu icon and
Msmsgs.exe don't do anything. When I double-click them, the pointer
changes to pointer+hourglass but then it goes back to pointer and
nothing else happens.

Any ideas?

BTW, I'm talking about *Windows* Messenger that comes with XP and NOT
Windows *Live* Messenger, successor to MSN Messenger.
.