New problem with a seemingly unchanged LCS.

I'm running LCS 2005. I recently have ran into a problem where none of my users can REPLY to other users. Everyone's status is shown correctly, and we can all send an initial message, but any reply gives the error 'he following message could not be delivered to all recipients, possibly because one or more persons are offline'

Well, that's for most people. For some, they get no error, but the message is never sent. The person who sent first can send as many IM's as they want, but the replies are never sent.

Around the time this started I installed VMWAre server on the machine... but that's pretty unrelated. Not sure if they happened at the exact same time.

I have since removed VMWare, but still have this problem. I started to try a SP1 install, but it gave me some error about a domain prep, forest problem... haven't dug into that yet.

No problems in event viewer