"I've also made sure the correct bootloader is on it (I burned it using Nick Gammon's programmer sketch). "
I think Nick's sketch sets the clock source to low power crystal: low fuse byte= 0xFF.
I believe setting it to full swing crystal, 0x7F, works better.
LFuse = 0xFF
HFuse = 0xDE
EFuse = 0xFD
Table 9-1 of 1284 datasheet:
Device Clocking Option CKSEL3..0
Low Power Crystal Oscillator 1111 - 1000
Full Swing Crystal Oscillator 0111 - 0110
Also see Table 27-5. Fuse Low byte, for info on the upper 4 bits of the Low fuse byte.