Pues algo no estás haciendo bien... Eso de signature verify suele salir cuando vas a flashear una ROM que no está firmada, y normalmente los recoverys tienen una opción para que se salte la firma y la instale, me suena a que por lo que sea no se te ha cambiado bien el recovery. Si ya tienes STOCK ROM 4.0.4, vuelve a intentar flashearle el recovery original (no el nexus ni niguno de esos, debe ser el original del movil)...
