I've been having this same issue, except it's with my two Gmail accounts. Sometimes I get notifications right away when an email comes through, but most of the time I don't. I won't get the emails unless I refresh the inboxes myself.
I thought it might perhaps be an app I downloaded interfering with it. I read a comment in the app market that someone claimed Advanced Task Killer was messing up his Gmail. I uninstalled ATK, rebooted, and then my email was fine. But a few hours later, I was back to having the same issues again. It's getting pretty frustrating.