No notifications on iPhone 4 running jailbroken iOS 6.1.2
It appears that this was caused by restoring an iCloud backup from a previous install which had been hacktivated. Notifications will not work with a hacktivated iPhone, and it seems as though they won't work with a restored iCloud backup of a hacktivated iPhone either.  

The solution is therefore to restore the jailbroken image and set it up as a new phone. This will then activate with Apple's servers and notifications will work.