Don't forget to include decoupling capacitors, it won't work without them.
One thing that I noticed is that if I disconnect the Vcc/GND wires from the Arduino board, the power LED that I've put on the breadboard still has a faint light,
This implies you have disconnected power and ground but left the signal wires going into the chips. That is a good way to kill them. Never put a signal into an unpowerd chip.