I've tested repeatedly on multiple devices with multiple iCloud accounts.
It works with the Mail App running, and with the Mail App closed (by manually killing it from the multitasking bar.)
I suggest that people check their notification settings, and make sure notifications are on for e-mail.
My mail message notifications appear on my device within seconds after sending mail to them.
If you've checked your settings, try deleting your iCloud account and adding it again, or restoring your device from backup. (make sure you backed it up first!)
If all of that fails, then perhaps there is a problem with your iCloud account -- and you'll need to wait for Apple to get it working again.
As many people have pointed out, Push does work for iCloud. I'm not sure what the Apple Rep was trying to say to the OP, but the subject of this thread is wrong.
There is Push Mail in iCloud and it works beautifully (for many).
If it's not working for you, check your mail settings, check your notification settings, try re-adding your account, try restoring your phone. If you have more than one iOS 5 device, try the account on another device.