A solenoid is basically an inductor. The coil of wire stores energy in a magnetic field. When you cut power to the coil, the field collapses and discharges a relatively high voltage spike back through your circuit, right into the FET. To protect the FET you need a good fast breakdown Schottky diode to drain the discharging coil.

Some FETs are packaged with flyback diodes. Look at stepper motor circuits; it's the same problem. I use Freescale MC33886 half H-bridge drivers (rated at 5A) for both solenoids and stepper motors, no extra diodes required.