Hi everybody. I was struggling with icloud mail push notification for long.
What I've found out is that it fails on wifi. On 3g it's OK.
It's not automatic: if you are on wifi and switch on 3g, you have to wait for some time before it start working.
If you reboot the iphone, push notification start to work immediately.
Talking with Apple Support, they gave me TCP/UDP ports to configure my firewall properly, but obviously this configuration didn't solve anything (and I was sure of that even before doing it).
Since it was the eve of ios7 release, I decided to wait some more time before migrating email account on another provider with push notification working (because, of course, the problem happened only with icloud mail).
Ios7 alone didn't solve anything, however in the last days something has changed.
I don't know if it's general, but now my icloud push notifications are working on wifi, too.
I've had the problem of unreliable push notifications right from the moment I switched to using iCloud for e-mail a couple weeks ago. E-mails only download x hours after they were sent, mostly when I manually update in the mail app. I've already missed an important appointment because of this, probably reverting back to Yahoo mail soon.