Unexpected voltage drop
The Arduino regulator does not Supply enough current to drive a relay coil, and as a result the voltage drops. To drive your relay properly, you need a driver circuit, which Wired explains better than I would:

How To Move Big Electrons With an Arduino

The reason why it works with a USB cable is because it supplies the 5V directly to the +5V net, without going through the series regulator.