Weird. It might be coincidental, but I just turned it off and back on again, also, and my me.com messages are now being pushed.Since I turned on Find my Phone in the iCloud settings, this has been working fine. Rebooted the phone. Email definitely quit. Receiving mails through without a hitch now.
Turned Find my Phone back off again and it's still working so may be coincidental.