Fixed.
More than creating a Provisioning Profile and enabling Game Center inside, you also need to Add your app on iTunes Connect. You need to go to an extremely strange process where it ask for the release date of your app, the price, some screen shots and icons, but once done you will be able to enable Game Center for real.