My STK500 is not the original one but a cheap clone. Anyway, the problem only appears with one of the boards...
The expected value is always 0x14:
avrdude: stk500_getparm(): (a) protocol error, expect=0x14, resp=0x90
And, at the end of the verbose output I get:
avrdude: stk500_initialize(): (b) protocol error, expect=0x10, resp=0x90
avrdude: initialization failed, rc=-1
Double check connections and try again, or use -F to override
this check.
I've checked fuses, signature and lock bits on the affected atmega and everything seems to be fine. This atmega comes from a batch purchased from eBay so I'm beginning to think that this uC is somehow faulty.