Two hours isn't too bad, but is a little sluggish for this forum.
Jeff, when you say ColorNick says Messenger is on, have you made sure you've quit it properly? Closing the Contact List only reduces everything to the System tray/Notification Area.
Other possibilities include Windows Messenger running invisible. Check for msmsgs.exe in Task Manager (Processes tab) and kill it. Also, if there's any stray msnmsgr.exe, which is MSN Messenger, kill them too. This should allow ColorNick to be installed.
Failing that, just use the tutorial above