Your major problem is that Darlington transistors, such as the TIP120, are very sensitive but not very good when turned on. If you look at the data sheet, on page 2 you'll find Vce(sat), which is the voltage across the transistor when it is fully on. At 3 amps of current and 12 mA of base current, the voltage is 2 volts.
Now, it's true that you have not specified your solenoid current, but it's also true that your base current will be no more than about 1 1/2 mA. Try measuring the on voltage across your base resistor, and you'll find it in the vicinity of 3 volts.
So, the first thing you need to do is increase your solenoid voltage by about 2 volts in order to compensate for the voltage drop you know you'll get. The second thing is possibly to decrease your base resistor in order to increase base current.
EDIT - A more complete circuit will look like

simulate this circuit – Schematic created using CircuitLab
It's true that a power MOSFET will produce less voltage drop, so you could stick with 12 volts, but there is a caveat. Arduino output voltages are not high enough to reliably drive the gate of a "regular" MOSFET. If you do decide to try this, you must be careful to get a "logic level gate" FET. If you don't, you may well find that the FET drops even more voltage than the TIP120, and it may vary wildly from unit to unit, with Murphy's Law dictating that you'll end up with one of the bad ones.
Regardless of what you use as a switch, you MUST include the diode. If you don't, the transistor will die sooner or later.
Also, you have never specified your solenoid current (I mentioned this before). If the current is more than (let's say) 1/2 amp, you'll need to provide a heat sink for your TIP120. Using the data sheet Vce(sat) numbers as an example, if the transistor is drawing 3 amps and dropping 2 volts, it will dissipate 2 x 3, or 6 watts, and without a heatsink it will self-destruct. The actual dissipation, of course, will depend on your current, as determined by the solenoid, and the voltage, which will depend in part on how hard you drive the base.