Habe ähnliches Problem,
hast du es über direkt avrdude direkt mit "-c arduino" probiert ein beliebiges hex, zB.USBAsp-Bootloader darauf zu laden
bei mir liegt es an dem lfuse, muss morgen mit HV ändern
wobei dein Fehler erst mit http://www.ladyada.net/library/arduino/arduinoisp.html aufgetreten ist, mit dem ISP aus dem Example, hatte ich eine 000000 signatur für mein m328P (1e950f), also liegt es am lfuse (bei mir)
Warum schreibt AVRDUDE von "Stk500", obwohl ich als Protokoll "usbasp" angegeben habe?!
Kommt von … kp würde ich gerne auch wissen
aber du muss -c arduino benutzten, weil du das Arduino als ISP benutzt (unsicher)

Hoffe du updatest dein Erfolg!