The error message in the title of this post seems to be a common one!
It occurred on a site I was working on a while ago and I thought I would note down the fix that I used.
Simply; I rebooted the GCs (in fact both DCs as they were both GCs and the only DCs/GCs in the network).
For a little more background, I had been installing a new Exchange 2003 organization from scratch for a company migrating from GW. Everything was going well until we tried to connect an Outlook client to a mailbox. The mailbox worked fine using OWA but not Outlook.
I did a little searching and found that after installing Exchange for the first time certain processes do not complete on the GC until they are rebooted. So having done that, everything worked fine.
Now I am not sure that this will fix everyone’s problem with this error message but it is certainly worth a try!