I'm using 3GS on 4.1, I had alot of trouble to begin with but left it over night, kept notifications off, installed PushDR, restarted my phone, turned notifications on and off and it worked
I think most of the trouble is due to two factors. Hacktivation, which always leads to trouble with push. And user difficulties with the procedure. If the phone is activated normally and the procedure followed perfectly I believe most of the current issues would be eliminated