How old are your accounts?

This individual also had slow Gmail issues and his account was very old. His issues were resolved when Gmail moved him to a new server.

http://www.gabrielweinberg.com/blog/2010/06/my-gmail-is-fast...