One thing I note - you should have a resistor between the output pin and the gate of the MOSFET. The gate is, to all intents and purposes, a capacitor. When you first apply power it is equivalent to a short circuit, rapidly changing to an open circuit. The initial current into that capacitor is known as the "inrush" current, and can be quite high, but short lived. If it exceeds the 40mA that the IO pin can provide (an ideal short circuit is 0? resistance, so Ohms Law says that will cause infinity amps to flow), which is will be - albeit for a short time - you risk killing the IO pin. You need a minimum of 125? resistance in that connection (R=V/I = 5/0.04 = 125) - slightly more is better, so say 150? or 220? should suit it fine.
That said, have you thought that maybe it's simply the fact that it's in a breadboard that is causing your problems? Breadboards have notoriously bad pin connections, and chips are especially bad due to the limited length of their pins.