Yes, been noticing that for the last couple of weeks. I never had this problem until the the latest update. I found that other apps are slow to sync.
I checked all the settings for the phone, apps and account and everything is kosher...
I tried clearing the data and cache, that worked. I also tried turning off Gmail sync, then turning it on again...presto. All the messages arrive with a notification.
I've seen zillions of the exact same gripe on forums everywhere, so I guess it's not me or my phone!