anche io ho fatto una cosa simile, anche se con un LCD I2C e con 8 rele con optoisolatori e non ho avuto questo problema.
Sinceramente però io alimento tutto non da arduino ma da un regolatore 5V che mi sono fatto a parte. Metto solo a massa comune l' arduino.
Penso che l' assorbimento totale tra LCD, relè, ecc... sia eccessivo.. inoltre se puoi regola anche la tensione 12V.