MarkT:
The way your arduino got damaged is probably excessive voltage spikes on the supply. You are lacking decoupling on the 12V supply, which allows spikes due to stray inductance in the power wiring. If the free-wheel diode across the solenoid fails this could also have big repercussions.Use at least 100µF across the 12V supply, more is probably better.
The ESCs are going to throw all manner of large spikes on their power, you should never be using that power source for anything sensitive.
I'd power the Arduino separately from the ESCs, and the solenoid.
I spoke to my knowledgeable colleague (Electrical Engineer) today, and he marked up the drawing to include a couple of caps across the Arduino supply, as well as a diode in line. Similar to what you suggested.
Schematic has been reverted back to original design, except now with protection caps and diode:
He explained that when the solenoid and/or motors draw current from the battery, there could be an initial voltage drop going to the Arduino power input (VIN). If the Arduino is crunching code while input goes below a certain amount, it could have caused issues.
He also said the LED's shouldn't have much problem with reverse voltage. If it blows it blows 
I will try this and see if it works.