Actually, it's not whether or not the iPhone is unlocked, but when it's activated. Factory unlocked phones requires no specific sim card to activate, therefore the security tokens are created from the Apple server. A hacktivated phone (a phone activated by quickpwn, pwnagetool, or redsn0w), does not activate with the ATT server, thus making it not have the security tokens.
To answer your question, a factory unlocked phone will activate legitimately, therefore the Push problem shouldn't occur. That is, if you activate the iPhone first and then jailbreak it.