Hi, Michael

Could ever your Pic have a RESET when power applied to your relay ... mmmmh ???

That could be a very good explanation ...

do try a LED instead of the coil ... just to see what's happening ...

sooo ...

1) do you have a BIG tank capacitor on your pic supply ( say 1000µF + )???
2) do you have the .1µF capacitor between vdd and vss ( the closest to the Pic )
3) did you think to the reverse diode ( 1n400x) // on the relay coil ???

Alain

PS ... once more: a scheme IS necessary to the troubleshooting !!!