I am using an original iPhone with t-mobile USA and I finally got push notifications to work! I don't know if this has been already posted somwhere but I couldn't find it using google so here it is.

Add http://cydia.iphoneil.net to cydia's sources

install push fix

after reboot, re-install apps that use push notifications like beejive, for example

If after this they are still not working, turn off and turn back on notifications under settings.