Hi Amit,
Having recently had to go through this issue let me try to share the steps that helped me.
1) I assume you have the basics right, like POP3 or IMAP enabled in GMAIL.
2) Yes, I can see that you have said so above, but please bear with me.
Given that there are two scenarios I can envision
1) You are working on a local installation using WAMP / LAMP etc… OR
2) You are on a hosted environment ala Hostmonster, GoDaddy etc…
Either way, create a simple instance of wp locally. Add the ‘Post by email’ plugin to it.
Once this is done, test connecting to your account. It should fail. If this happens then you are experiencing exactly the same issue as me. In which case, the resolution lies in the PHP & Apache settings. You will have to explicitly enable the imap, SSL, setenvinf etc…
the solution is described succinctly by Nikunj Bhat in this blog post. although the context of the post is sending email ,the settings apply universally when manipulating email via PHP & Apache.
http://nikunj-solutions.blogspot.no/2011/08/send-email-using-wamp-server.html
If all is well (not just downloading email using a mail client) locally, then the same applies but you will have to speak with your hosting partner to enable the same modules as described by Nikunj. Having this list will make the conversation easier.
I have hostmonster as my hosting partner & so far I have discovered that the support folks say the ports are open but the FAQ says the requirement for ports <1024 is to have a dedicated IP. I have yet to figure out where to enable these settings in the shared php & apache config.
hope this helps.
Prakalp.
