That's a really strange issue you have here. Never heard of anything like this. Could it be possible that some aggressive filtering exists on your network that would disallow your iphone to connect to Apple's push servers ?