I agree the IDS block is the most likely culprit, but without knowing more about the setup those clients are using its tough to say. Are all affected users connecting via secure IMAP on port 993? If so, what hostname do they have configured and were they having any trouble reaching the hostname directly in a web browser or via telnet connection? If you can get a ticket submitted on this one I'd be happy to help dig in.
Kyle Kerst
IT Coordinator
SmarterTools Inc.
www.smartertools.com