I am having the same issue. I tried rebooting, changing to fetch and back to push, deleting account and adding back, all with no luck. Every now and then and email will push through, but not reliably.
iCloud is terrible. I want mobileme back. push is intermittent and my folders are not syncing. not to mention you only get 3 aliases. what a terrible launch this has been.
I don't think it's iCloud being horrible and not pushing. I think there's something in ios5 that's causing this bug. Push won't work for me, currently using iCloud. Won't work with yahoo, which for me was flawless on ios4, or gmail. I just had my phone swapped out and it still won't work with the new one.
It would work on my iPad, first gen when I had it as well (just sold it earlier this week) but wont work on my iPhone 4 with ios5. iPad had ios 5 on it as well. Fetch works. But not push.