I managed to find the answer, turns out whoever I bought this chip from (and the other chip) had set the boot loader lock on, and since my command was trying to set the boot loader lock off the command was failing.

Avrdude reports that the lock is read back as 0x0C, which is my command (0xFC) minus the already sex lock bits (0x0), so I had to change my command to: `-U lock:w:0x0C:m`