Which seems odd since a reset is required for this to happen
Indeed. You wouldn't be able to read the fuses with AVRDude if RESET wasn't working, either. RESET is fundamental to talking to the chip with a programmer...
The bootloader does flash the LED upon power up, though
This is odd too. Assuming that you're using Optiboot, the bootloader should not run, and it should NOT flash the LED, on powerup. This is the "Adaboot fast start mod" that starts the sketch immediately on powerup, and only attempts uploading based on an "external reset."
Any chance that this somehow contains the wrong bootloader?