I have the same problem... I'm not quite sure how long ago it started to happen, maybe 1-2 months ago. Basically getting new mail notifications sometimes works, and sometimes it stops working. Hitting refresh on the e-mail application seems to restore the functionality at least for a while.

I don't know what causes it though. I don't have on my "daily driver" phone any tweaks (except FasterN9), so my best quess is it's some data that has been accumulated and causes this problem. Not sure if resetting the e-mail database would fix this or just cause more problems.

I'm not at the moment too worried nor motivated to find out the reason, since it kind of feels good sometimes to only check e-mails when I want to (the notification always makes me want to check it even if it's not that good a time).