Pedro,

For starters you can put a dump diode across the relay to eliminate any Bemf when the relay turns off.

You could also try try putting an opto coupler between the pic and the relay. I remeber seeing a post a while back with some guy trying to run a hammer bell or something and had simialr probs. Do a search on relays in this forum and you should find a few answers.

Cheers
Squib.