How can I get Google's two-step verification to work?
The answer is that you have to use a standard computer, log into your google account 2-step verified google account, go to authorise applications and sites, and set up your android device.  Google have said that 2-step verification will not work yet on android, so they have provided this work around for now.

Here is the link where you create a password to authorize your device:
https://accounts.google.com/IssuedAuthSubTokens

They will then give you a password which you can enter into your phone, allowing you to keep 2-step verification enabled.