Issue resolved with a bit of help and hint form the Nokia Russian customer service. They said my account was registered not with my regular Gmail but with Nokiamail (Yahoo-Nokia partnership service).

I was able to login with that @nokiamail.com account instead of @gmail.com

Why did the system switch from my Gmail? I still don't know that, but it is certain that it did since my gmail was listed a secondary email. I switched it back to primary and my N9 login to app store just fine.