Sometimes, the error messages that we get are absolutely misleading. This is one of those cases where you get called to a server for a mail problem and end up wasting a couple of hours on a problem that could have taken mere minutes to fix.
The symptoms are pretty simple....
