So to your delight, we have discovered an app in Cydia that would fix Push Notifications on your iPhone instantly. Its called Push Fix and all you need to do is install the app, no more tutorials or hacks to follow.
The app is not available in the default Cydia repositories so you will need to add http://cydia.iphoneil.net to the list of sources and then refresh. Once done, simply find and install 'Push Fix' and reboot your iPhone. Now make sure the Notifications are turned on in the Settings app and try it with any app from the App store that supports Push Notifications, such as Beejive IM.
From what we have tested ourselves so far, Push Notifications is a great and innovative new technology by Apple that helps you receive notifications from apps without having to ruin any battery life over background apps but the thing is that it comes with a price, which is that it runs on the cloud.
As a large community of the iPhone already seems to be having problems with this new technology, its hard to say how Apple will manage to make it survive in the long-run, or perhaps Apple will be left with no choice but to look further into enabling background apps in future versions of iPhone OS.