Como YouTube te dirá que la contraseña se cambia en Google, ¿has intentado iniciar el proceso directamente en Google para ahorrar ese paso?
https://www.google.com/accounts/recovery
Debes ingresar la dirección de la cuenta + el captcha, después se te mostrarán las opciones de recuperación disponibles (parcialmente ocultas), debes seleccionar una de ellas... si seleccionas la opción de enviar un mensaje de correo a la dirección que aparece allí, entonces recibirás otro mensaje con un enlace largo que te permitirá cambiar la contraseña directamente.