I have iPhone 4s running latest firmware and started to get this notification when I open apps that use push notifications. It stared happening when reset my iPhone. After resetting it I had to input all my password again which was strange and I started to get this notification to connect to iTunes to use push.