There is another thread in the forums about Gmail and Mail.app, someone there sugested taking a look to this link:
http://5thirtyone.com/archives/862
There are few extra steps to properly setup Gmail IMAP and Mail.app. I was having the same probles you describe here but after following the steps in this tutorial all is working ok for me.
BTW, google has posted now 2 sets of instruction for setting up IMAP one for 10.4.X and other one specific to Leopard...
Hope this helps
Cheers