I have had a bit of an issue with "push" gmail for awhile now. I got my droid on launch day. Whenever I send myself an email in gmail on the web, it takes up to a full 2 minutes or so to "push" to my phone. I just tried sending an email to myself from a different address and its the same story. Sometimes its quicker than other times, but it tends to be on the order of minutes. Meanwhile, the web client is much faster. I also notice the same issue with updating the status of mail. I'll archive something on the web client and it won't update the status in my phone.
Its really annoying. It feels more like pull email that updates every 3 minutes. The whole "auto-sync" thing just makes it sound like it really is pull and has to sync to get everything, hence the timestamps. Its pretty fast, but I don't consider a few minutes to be true push. I'm glad to hear its not just me though.
Everyone with this issue:
Go post at the bug report
http://code.google.com/p/android/issues/detail?id=5383
Don't forget to star it. Maybe if we get enough numbers we can get Google to do something about it. Or at least explain why this is happening.