It sounds like the diode is not working Maybe a filter cap across the solenoid would help. (470uF /25V)
Hi,
Can you post a picture of your project,showing where you have connected the power wiring?
The wires that go to the solenoid and the source of the MOSFET should be connected DIRECTLY to the battery.
This means that no solenoid current will flow in the two UNO power supply wires.
Also try not to use pins 0 or 1 as they are the programming pins for the UNO
How much current does the solenoid use?
What is your power supply?
12V is a bit high to power the UNOs, what do you have them controlling and supplying 5V to?
Tom.. 
Good point about the solenoid wires Tom. That's probably frequently overlooked.
Thank you, Tom. Indeed, connecting the ground cable of the solenoid directly to the power supply and, therefore, further away from the Arduino's ground pins solved my problem.
The wires that go to the solenoid and the source of the MOSFET should be connected DIRECTLY to the battery.
Thank you, Tom. Indeed, connecting the ground cable of the solenoid directly to the power supply and, therefore, further away from the Arduino's ground pins solved my problem.