Ask HN: Google 2 factor authentication security?

I've got it enabled & it works well using the authenticator android app. I'm worried about the android device though: If I lose it someone has a device with both the authenticator plus android apps (gmail etc) that allow access.

Is this enough for the crook to take control over the account? i.e. Can one change the master password from there or will I always be able to kill the device specific password with my PC + Master password?