I switched to using IMAP on my gmail accounts (tring it out for a month, and depending on how I like it, I'll stay or switch back).
I used to have the same problem when I used gmail pop in 10.4, to fix it I would have to remove and recreate the GMAIL pop account in mail.app. What I would find is that even though I kept setting GMail pop to use SSL, it would keep reverting to different ports instead of the SSL ports like it should have been, and was set to.
What happens if you remove and recreat the email accounts in Mail for the gmail account? And, have you tried IMAP instead?