Does your circuit reside in a metal box..and did you connect it to a ''ground'' connection? I don't tell nothing new...power relays are able to create tremendous disturbance...and your uC might suffer this...sometimes.
Edgar