mat: If I try what you suggest won't the resistor allow a current to flow all the time? Or have I misunderstood how it should be connected?

sayzer: The code is definitely working ok - with no load across the relay it will switch on and off without any problems every time. It's only when there's a load across the relay that the pic will reset when the relay switches.

The fuses are everything off except PWRT (or 0x3F31). (Incidentally I'm using a bootloader, so this is the fuse configuration it defaulted to...)