what is the cap-resistor across the relay coil supposed to do?
From what I understand, it limits the rate of change in the voltage across the contacts.

Here's a thread where someone had a similar problem. Snubber seems to have helped.
http://www.picbasic.co.uk/forum/show...hlight=snubber