I'm a bit stumped. Connecting that 10K, either to 5V or ground, either one or the other, should have kept the LEDs off until the Arduino started. Your diagram shows a common ground between the Arduino and the mosfet. That's definitely true, isn't it? Also I think it's still worth trying another MOSFET, in case that one is faulty/damaged.