Salvo que tuvieras hecha una burrada en el cableado, eso tiene pinta de que dejas sin electricidad al arduino del pico de tension del rele o la electrovalvula.
Tienes alimentacion separada para el arduino y la electrovalvula o no?
El rele lo activas con un transistor o lo has puesto directo al arduino?
Pusiste un diodo para que se "coma" la tension inversa de la bobina?