After uploading an app the first time you can't change the app id anymore! Your issue is that your are using a wildcard app id profile. You do not need to change the app id, you need to change the profile (created on iOS Provisioning Portal) for it.
When the app id you set in Xcode has been something like com.example.MyAppName
and you created an app id profile on iOS Provisioning Portal which is only ABCD123400.*
(ABCD123400 is your developer ID) or ABCD123400.com.example.*
then you created a wildcard app id profile.
To use Push Notifications or Game Center you need to use an explicit app id profile. To get this one you need to create an app id profile for ABCD123400.com.example.MyAppName
(exact app id, but don't change it, just replace the *-char!).