Managed to get it working now. I only tried one of my accounts before, and it seems that with that particular account, there is a problem when using @gmail.com rather than @googlemail.com. It's probably because I didn't migrate the account over to gmail.com despite all those annoying reminders that I kept getting every time I logged in using a web browser.
Judging from the comments and some bits I read elsewhere, they were 'forced' to remove it from the marketplace. However, I'm a loose cannon and don't care much about potential legal problems or cosying up to corporations.