Ground bounce is a common problem, and so is brown-out (low input power) when switching heavy loads. Using the same Vin for the relays and the regulator that feeds the micro is not a good idea unless you use a lot of bulk capacitance at the input of the regulator as well as a modest amount of capacitance (10uF to 100uF) at the output.
You also want some low ESR capacitors (like tantalums) on input and output to deal with fast transients. 10uF on the input and 1uF on the output are very common.
And as the others have mentioned, a solid ground is important. A single point ground is best, and a solid ground plane is good. Also keep the relay power lines and loops short as possible, and keep them as far away from the micro and its power and reset lines. You don't want the relay power loops generating large EMF signals to the micro's connections.