Thanks for the quick response - moving the relay farther away from the Arduino (now about 70cm) does seem to do the trick!
I also put a layer of tin foil between the arduino and relay.
I never would have guessed this.
Ideally I'd like the relay and board to be inside the same box - is there any way to reduce the interference at close distance?
Thanks again.