All of a sudden, when I try to add a contact in IM, and do a "search for user" I am getting strange responses. If I put just the first initial in, it will return a list of users. If I put 2 or more letters in, I get :

"You have entered an invalid user ID" on the Desktop and
"Object referenced by DN does not exist" on the IM server.

If I try by Username, I get the same errors.

An LDAP browse seems to be fine.
I have no idea where to start looking, any ideas is welcome.