Is it just me, or do the notifications only work when the device is not locked? If I lock my device and I get an email, it doesn't vibrate and show me the notification. Either that or notifications aren't consistently sent.
Check your Notification settings. Settings -> Notifications -> Mail. Make sure "View in Lock Screen" is enabled.