I don't see a resistor on the led either, that could be drawing the power supply down enough to make the relay unreliable. You are probably frying your Arduino outputs. Might slow things down too, I know I can't see a led change state in a few microseconds.
TomJ