I think I have an idea that could fix the GameCenter issue ....
As per our different individual attempts ... the only way to make Game Center work, is to restore to stock iOS 9 without the backup data ...
So If we backed up our data to iTunes, then restored to stock iOS 9; Game center will work ...
After that, we will need to restore only the important unique data through a 3rd part tool (forget about facebook and instagram data for example) ... I remember there is a software that can dig out the backup, I'm sure there is a way to copy the data back or generate a new backup (without the settings or configurations, just the important app data like games, SMS, phone log, ..etc, iCloud has the rest of contacts, calendar, mails and so on)
If anyone knows a way to do that, and test it ... I think it could fix our issue 😀