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.