In my experience, once you switch the fuse settings to an external crystal, if there is a problem with the external crystal, then the processor will not communicate through an ICSP. Once the crystal issue was resolved everything worked. Your experience sounds similar to mine but not identical.
Do you have anything connected to the board?
I did have, but I took it it all out to go 'back to basics'. I connected the 'L' LED, but that's all. (Aside from the crystal, of course)
Your point about the crystal is intersting. After I'd burnt the bootloader, I could upload Blink fine the first time. Then I changed the delay to 100ms (so that it would be obvious the program had definitely uploaded), and sometimes it would upload, sometimes it would give the verification error. I was never able to upload more than 2 programs without having to re-burn the bootloader.
It would be simpler if I were able to use the FT232 breakout I have... My first thought was that it's a problem with the timings, as maybe they're never 'syncing'?
I'll try another few crystals and double check the crystal setup and report back.
Thanks for the advice so far.