Apple's e-mail notifications on the iPhone have always been hit-or miss, in my experience. Much of the time they work great, but far too often I won't get any unless I actually open the Mail app. This is true of both IMAP and POP accounts I have had ...

I'm going to say it's not you but Apple =P