I had the same problem with my dx. Worked fine for about 2 days and then I stopped getting email notifications. Settings were correct and re-booting didnt help. I know it only takes 30 secs to check manually but that is just clunky for such an advanced smart phone. Id go all day without an email only to find out that when I checked gmail, Id have unread messages sitting stale for 6-8 hours. Unacceptable for me coming off a blackberry.
Ended up trying a factory reset and starting all over. Now my email seems to be pushing to me properly after 2 days. I hope this problem doesnt spring up again.