La cuenta de Google no guarda las contraseñas de Wifi, aplicaciones, etc.

Es una "característica" bastante conocida. No te preocupes, tus datos es respaldado allí - sólo no lo hace restaurar . Y ni siquiera se puede borrar realmente allí. Así que de alguna manera, es "seguro"...

Cosas que quizás quieras buscar en este contexto:

• ¿Qué se sincroniza exactamente con Google?
  Subraya lo que he dicho antes, y también muestra formas de comprobar lo que está "sincronizado"

• Copia de seguridad de Google: Múltiples dispositivos con la misma cuenta: ¿qué ocurre en la restauración?
  Un montón de detalles sobre cómo funciona (y a veces falla) ese "Google Cloud Backup"

• ¿Qué información respalda Google?
  Bueno, el título lo dice todo :)

• [Problema 17354: La "Restauración automática" rara vez funciona, y sólo parcialmente](http://code.google.com/p/android/issues/detail?id=17354 "Google Issue 17354: "Automatic Restore" rarely works, and then only partially")
  Lo que ya indiqué arriba, y muy probablemente la respuesta a tu problema actual. Tenga en cuenta que este ticket se abrió en junio de 2011 - y todavía tiene el estado "Nuevo". Uno de los comentarios también incluye una posible solución:

  Esto es lo que he hecho y ha funcionado. He restablecido el dispositivo de fábrica (de nuevo), y luego en la primera pantalla (donde se elige el idioma), lo apago. Puse una tarjeta sim diferente, lo encendí y luego procedí a la configuración normal. Esto funcionó en mi Nexus 4.

• Heise sobre las contraseñas WiFi indelebles (Alemán)
  Si no me crees lo de las "copias de seguridad indelebles", esta es mi referencia. El artículo está en alemán, y la editorial (Heise Verlag) es una de las fuentes más famosas y de mayor confianza aquí en Alemania, en lo que respecta a temas de TI.

Hay muchas más referencias que podría dar, pero sería demasiado para aquí. Así que una última pista: comprueba los enlaces de las preguntas "enlazadas" y "relacionadas" en las preguntas y respuestas de la ASE que he enlazado aquí.