Have SweetIM and/or SmileyCentral installed? PLEASE READ
Try readnig that thread and see if it helps with your problem.
It's worth checking the Add/Remove Programs (Programs & Features on Vista) for those two programs as sometimes they can be installed even if you don't think they are and they are both known to conflict with Messenger Plus Live and cause the problem you are describing