A few of the developers have encountered the issue when they delete the project without deleting that client id. We can fix it. :) Do make sure to look for any deleted projects or ask other members of your team who may have created the client id with the same details (most common reason).
Ping me through my G+ profile if you need help.
Update: Dec 16, 2016: We have made some changes and most of you should not be seeing this message. Most of these errors were due to the fact that when a project is deleted they are soft deleted (and completely deleted after a few days) because we do allow a developer to undelete. There can only be one client id with a given package name and SHA1 hash of the cert and that is why you get the error.