Read my blog entry "Byte and Switch" -- it covers this exact scenario.
The short answer is that you need a freewheeling diode to conduct the current when the MOSFET turns off; the solenoid has inductance that stores energy in the magnetic field, and when you turn the MOSFET off the inductance will generate however much voltage is necessary to continue flow of that current. The resulting voltage pulse will cause breakdown in the MOSFET which causes the damage you are seeing.
You should also add a couple of resistors, one from microcontroller output to ground, to make sure it's off when your microcontroller is in reset, and the other from the microcontroller to the MOSFET gate, to add some resistive isolation between your power switch and your microcontroller.
edit: I just noticed you're using a BS170 MOSFET. Have you looked at the datasheet? This is a poor choice for a MOSFET used as a power switch from a microcontroller.
First of all, the MOSFET is specified at 10V Vgs. You're supplying it from a 5V microcontroller. You need to make sure you use MOSFETs that are "logic level" and have on-resistance specified at 4.5V or 3.3V Vgs. (I suggest you not use ultra-low voltage MOSFETs as there's a possibility of it turning on weakly when you think it is off.)
More importantly, it's a small TO-92 MOSFET specified at 5 ohms max Rdson at 10V Vgs. This MOSFET is fine for very small loads like LEDs drawing a few milliamps. But solenoids generally draw tens or hundreds of milliamps, and you need to calculate I2R loss in your MOSFET for the current load it draws, and make sure that it doesn't cause your transistor to overheat. Look at the thermal resistance R theta J-A on the datasheet and you can estimate how much temperature rise there is in the part.
Use a MOSFET in the 20V-60V range that has a lower on-resistance -- as I said in my comment, we need to know how much current your solenoid draws if we're going to help you.