You don't really "format" a chip with a bootloader. I personally just uploaded the sketch, I think (it was 19th September) by using my "sketch uploader" here:
Or maybe it had a bootloader on it. The important thing is, you get your sketch into "low" program memory (where sketches normally go).
If you replicate what I had here:
It should work. Judging by what I posted further up:
Atmega fuse calculator.
Written by Nick Gammon.
Entered programming mode OK.
Signature = 0x1E 0x95 0x0F
Processor = ATmega328P
Flash memory size = 32768
LFuse = 0xE2
HFuse = 0xDA
EFuse = 0xFD
Lock byte = 0xEF
Clock calibration = 0x85
External Reset Disable.................. [ ]
Debug Wire Enable....................... [ ]
Enable Serial (ICSP) Programming........ [X]
Watchdog Timer Always On................ [ ]
Preserve EEPROM through chip erase...... [ ]
Boot into bootloader.................... [X]
Divide clock by 8....................... [ ]
Clock output............................ [ ]
Bootloader size: 2048 bytes.
Start-up time: SUT0: [X] SUT1: [ ] (see datasheet)
Clock source: calibrated internal oscillator.
Brownout detection at: 2.7V.
The chip had a bootloader on it, and the fuses are as stated there.
-Interrupts seem to work when I have the fuses set to use an EXTERNAL oscillator
I think you are getting confused. Interrupts work, whether or not you are using the external oscillator.