having same problem but my deivce is an ipod touch 4g not an iphone and my data carrier is a mix of comcast (wifi) and virgin mobile (3g/mifi), so I think that effectively rules out Yahoo! -> AT&T as the source of the problem.
I also sent a test e-mail to my iCloud e-mail account and push was also spotty there although that issue could just as easily have been my mifi..
I was able to get it working again after a "soft" reset (sleep/wake for 5s) but then it immediately stopped working again and couldn't be revived with the same trick.
just to make matters worse, after all that my yahoo push mysteriously worked again but then when I went to check the message the Mail app seemed to have trouble refreshing the screen, laying two or three things on top of one another...
All in all, it's maddening!