Arduino Mega getting hot and slowing down after firing solenoid

I've got an Arduino mega controlling some solenoids through MOSFETs. The solenoids run on 25V, and have a common ground with the Arduino's 5V. They have protection diodes on them. I have configured it to blink the pin 13 LED in the main loop() function so I can verify it's not getting stuck in loops or anything. If I just turn it on and leave it idling (waiting for me to press a button so it will do something), the LED blinks very fast, and within five minutes the Arduino CPU is hot enough I can't keep my finger on it for more than a few seconds.

When I press the button, (which should activate just one MOSFET/solenoid), the correct solenoid and another (often the same solenoid each time, but sometimes another one too) random solenoid will fire, and the blinking slows down to about half the speed it was going. If I press the button immediately after turning the Arduino on, I can fire the solenoid two or three times before it starts misfiring. Once it misfires once, the blinking never returns to its normal speed, and the solenoids never fire correctly until I unplug the arduino or press the reset button on the board.

The solenoids only misfire when their MOSFETs are connected to the arduino. (it's not a MOSFET malfunction).

I'm pretty much lost here... Are these temperatures normal? Can anyone explain the blinking slow down or the solenoid misfirings? If you need any more specific info, I can supply it...

Post your schematic - sounds like something is miswired, causing the current to be overdrawn.

Definitely need to know your circuit, power supply, which MOSFETs, surrent rating of the solenoids, and whether you run the wiring to the solenoids close to other wiring.