Well the pinout is right, the circuit is right, perhaps double check every point in the circuit has the voltage you expect using a multimeter ? A component might be faulty, or something is shorted out?Have you tried shorting the negative wire of the solenoid to ground direct (bypassing the TIP120)?
Perhaps the Arduino pin is shorted to ground, or not working? Does it control an LED/resistor combination?BTW passing 0.5A through the base-emitter junction of the TIP120 might have damaged it, hope not.You ought to get at least a cheap multimeter, its going to really help troubleshoot things like this.
Sure those TIP120's are kosher? Many semiconductors from eBay are fake/junk/rejects/wrong.