It turned out that after importing the game center package , I ended up with two manifest files. I had the Prime[31] AdMob already in the project, which comes with a manifest file. By the way this is normal.
After talking to the their support service they directed me to use the "Generate AndroidManifest.xml file..." under their prime[31] drop down menu inside Unity3D. This merges the two files into a single manifest. That problem got solved.
I also had to upgrade to the latest files, by downloading them manually, from the Prime[31] web site.
After this two steps I was able to get the Game Center to work properly.
I hope it will help, I am posting my interaction with the Prime[31] support