Hasta dónde puedo ver ese es el problema efectivamente.
Para faciltar tu tarea te recomiendo que Descargues el MySQL Administrator (yo uso la 1.1.9) desde
Cita: http://dev.mysql.com/downloads/gui-tools/5.0.html
Menu Startup Variables/Solapa "Security"/ tildar "use OLD Passwords" (creo que despues de esto deberías borar y crear nuevamente las claves)
Saludos