It is not uncommon for carriers to block certain services over their celluar network.
Can I ask why you are using IMAP and not active sync. As active sync uses http then carriers shouldn't block this.