There is no way to "fix" push. Apple is simply not letting you enter their private garden per se.
My understanding is this:
During activation process, a valid device will contact Apple servers for validation. If they see that you are using a valid sim card for your phone (IE: AT&T sim card on an AT&T phone), they will generate 2 digital signatures for your phone -- one for YouTube, and the other for push.
The signatures' public key is probably something your device knows, so it can make use of it to do what it needs to do -- talk to YouTube, and push server. The signatures' private key is only known to Apple, so there is no way third party can generate the signatures for you.
When a device is connected to the push notification server (owned and operated by Apple), the server will ask your device for the certificate, and use that as an authentication token. If you don't have a certificate, it won't let you in. Once you are in, Apple recognizes you based on that particular token. So when an application's developer -- say for example BeeJive IM 3.0 -- contacts Apple saying there's an update for so-and-so, Apple looks at the tokens and deliver the message.
The "PushFix" that was released a while back was a method to extract/inject certificates to your device, so your device can provide a certificate when requested.
This brings up a problem:
Without a proper activation, you won't get your digital signature that is unique to your device. If you used "Push Fix" to inject with someone else's signature -- chances are, that is shared by many many many MANY people by now, Apple doesn't know who to send the notification to... and so it sends to whatever most recently connected device... could be yours, could be someone else's. In theory, Apple could also ban the certificate from using Push, so no one will get the notification from that set of certificate. Additionally, in theory, Apple could also be sending your device's UUID to their push server, so they could ban your device from using Push services all together forever. Even worse, if they do have your UUID, they know you've made modifications to your phone (App Store doesn't have applications that will allow you to inject other people's signatures into your device), so they could in theory void your warranty.
So. How does Push suppose to work for Jailbroken users? In short, it doesn't. Not unless Apple release the private key for the certificates, so we can generate the certificates for you.
However, the release could benefit some people... maybe a small handful.
Say if you are me, and you have a Rogers iPhone, and a Rogers sim card, but you want to use Fido as your service provider (Yes, I know I should've just found a Fido phone instead, buzz off of my case), then the push fix have some merits.
When I restored my phone, I first used my Rogers sim card to activate it. As such, I get my own unique certificate from Apple to activate YouTube and push. Jailbreak using RedSn0w, and extracted my certificates from the phone. I then wipe it again -- so the carrier data and other stuff doesn't stick on the phone -- and hacktivated it using Fido's sim card and RedSn0w. Finally, I used the push fix tools to inject my own certificates back into my device, and of course, because no one else is using my own certificate, Apple will deliver my push notifications properly. However, from now on, each time I need to do a full restore, I must repeat the process to get my push notification to work -- well not really, I have my signatures stored safely, so I can just re-inject without having to re-extract.
I've heard some people use their iPod Touch certificate on their hacktivated iPhones, but I don't know the milages on that. Maybe it'll work, but probably only one device can receive the push notification, and you don't know which one it will be...
If you find an easier solution, please do keep us updated though. Would really love to know how to make the restore process easier for myself...