Just to make this easy to find as there are lots of people asking the same questions.
There is a problem with Jailbreak/Ultrasn0w meaning that if you do not activate the iPhone with its official carrier sim, push will NOT work.
I believe the dev team are working on this currently, but until then the only way to get push is to jailbreak using pwnage and make sure "Activate the phone" under general settings is NOT selected (redsn0w doesn't give you this option). You will then need activate using a sim from the company that the iPhone was locked to (AT&T etc). You can then put the sim you want to use into the iPhone and proceed as you would have done.
This method will then have you with a jailbroken, unlocked iPhone with working push notifications.
