The problem is systemic, including both systems, the push mail system, and the push notifications. I know my exchange server supports push, as it worked fine before I updated to 3.1.3. All of my friends on the same exchange server using jailbroken 3.1.2 iphones have no troubles with mail being pushed.
Nonetheless, I have tried gmail with activesync, and the issue is identical. It seems as though it is a network connectivity / timeout problem. I am suspicious that Apple changed the frequency of their IP "heartbeat" messages or something around the handling of them with this update. (perhaps to improve battery life).
Push notifications suffer the same problem as the OP. (Beejive, NotifyMe, GmailPush, etc etc). Sorry for not getting to into the details, I have given up finally and just use fetch for email and don't use IM clients on the iphone.
gary
I am having the EXACT same issues! I have searched and cannot find any one else that has posted about this exact problem!
It seems to work with no problems when I restore and set it up as a brand new phone and just install beejive, push works fine. But as soon as I load on my other applications and setup my email accounts, push dies. It will work for about 1 minute if i turn on and off airplane mode, but then it stops working again.
This is extremely frustrating!
EDIT: So I'm restoring once again (5th time for the night) and Push notification for Beejive seems to be working fine when I don't setup any email accounts. I'm going to leave it for the night and see if Push notification still works in the morning, if it does, I'm going to setup exchange again to see what happens. I have a big feeling exchange is causing push notifications to fail along with exchange push email to fail.
EDIT 2: So after some extreme testing by restoring and re-configuring my iPhone over 30 times, I have pinpointed the problem. Certain Microsoft Exchange setups. If I set it up without microsoft exchange, all push notifications work properly, as soon as a microsoft exchange account is added, push does not work properly. The occasional random push will come thorough but definitely not normal operation. For whatever it's worth, Google "Exchange" seems to work fine.
The good news is, I am playing around with iPhone OS 4.0 Beta 4 and THE ISSUE IS FIXED! Exchange push works perfectly along with Apple Push notifications! I was so close to going back to Android... now I just can't wait till official os 4 is out! Hope this helps anyone else experiencing this issue!
EDIT 3: So I spoke too soon, OS 4.0 Beta fixes the issue somewhat. What happens is Apple's Push notifications work properly but now exchange push doesn't work. After messing with my exchange server for a couple days I think I have finally came up with a solution. Create a new Active Sync policy in Exchange Management Console, assign that policy to the specific mailbox you are having problems with. I also removed HTTP Headers Information in IIS, not sure which one of those did it but it finally works, this time both Exchange and Apple's Push Notifications work perfectly. I am running Exchange 2007 SP1 on Windows Server 2008 with IIS 7.5.