Zimbra 6.0.9 IM remote server not found when both parties on?

[number9]

I saw this problem right after I upgraded from 5 to 6.0.9, but I thought I had solved it (the other person was not online and available). However, now we are getting helpdesk calls and I see that this is a reoccurring issue... has anyone seen this one:

6.0.9, try to IM someone, the IM box shows up, but in RED it states that the remote server is not found. Sometimes it does not do this, and it works. Sometimes, even when the remote person is in zimbra and is "available" for chat, it does not.

I could not find any bugs on this in bugzilla, and no forum results. Perhaps "IM remote server not found" is not a good search term? Any help would be appreciated. IM was one of those things that used to "just work" and unfortunately I now have people that want to use it (of course).