What key are you going to encrypt these passwords with? If you were to encrypt passwords in the cloud with a key that's stored on the device, you can't unlock the passwords on a different device (or the same device after flashing), which is the whole point of backing it up in the cloud. If you were to encrypt them with the user's Google Accounts password, the device would need to ask for that password on every startu…
The shared key could be backed up to Google's servers and encrypted using the user's password so in the event of a new device/flashing the shared key could be re-downloaded.
Then you only ask the user once for their password.