Gmail Account Hijacked - including Google Play Store
Last week I noticed a device under my Google Play account (My Devices) that is not mine, a phone on a Romanian cell phone company network. I also noticed that someone from Russia had accessed my Gmail account. I changed my Gmail password (the old one was alpha-numerica,random, with symbols) and turned on two step authentication.
The Gmail account seems to be ok. The contacts all there and no messages removed or messages sent by people other than me.
The only sign of the intrusion is about a dozen "free" apps ordered by that device. It included sketchy gambling apps, a child's game that from comments I read has adult advertisements, and ringtones. After I changed the password there are new "free" media on the account - books and various video. These appear to be from a different user - all in English as opposed to Russian and nothing sketchy.
My guess on how this started - I downloaded an app with about 100 reviews. The next day the "free" apps started to appear, and the unauthorized device also was added the next day.
My SGS 3 isn't rooted. For Jellybean it seems that I have to wait for a stable root, should be another few days.
I contacted the Play Store support and they were of no help. They referred me to Gmail support but Gmail doesn't offer phone support. I think only support on a Google Group forum.
Any idea how this could have happened and how to get this device off of my account? My PC's are secure and my primary PC is Linux.