Jay,
Are these users able to log in to webmail without issue? If they can't log in to webmail, you may want to check IDS settings. We've seen this behavior when the IDS settings are a bit too restrictive.
Derek Curtis
COO
SmarterTools Inc.
www.smartertools.com