Ah, yes okay that sounds precisely like my situation as well. Not so much the backup codes not working as Google's auth gatekeeper being moody, the last thing you want from a login system
Had I followed Googles own advice and relied entirely on these codes (which I thought I was doing) I would still be locked out of all those accounts, purchase history, Google Play Developer, etc.