Tim... As Elizabeth says, the LED/Resistor / Relay are probably what's causing your problems.
1. Don't put the LED in series with the relay. The relay (the type you have drawn is an automotive relay which probably takes 100mA or more, this would burn out a LED, though with your resistor in series the LED would light but the relay might not operate....2. As Elizabeth says, the 2N3906 is not a very beefy device, I'd use something bigger in a TO-39 case (2N4406 springs to mind but there's probably better newer ones - look for a transistor with a 500mA or more collector current (Ic) rating.3. When you're switching a relay (which is an inductor) with a transistor, ALWAYS put a reverse biased diode across the relay coil. When you switch the transistor off suddenly it can generate a back-emf of a few hundred volts on the inductor. Pop goes the transistor.4. The Hall sensor can work on 12V. If so you should wind up with a diagram like this:
I have:1. Used separate feeds to the relay and the LED though they are fed from the same transistor.2 Used a 2N4406 - datasheet here.3. Used a 1N4001 to catch any back emf from the relay switching. Beware - if you get this the wrong way round you'll blow the 2N4406!4. Left the base resistor at 510 ohms, though you could probably increase it up to 1K without a problem, depending on the relay current. the Base-Emitter resistor will probably be OK as a 2K2 , again you may have to experiment. I've increased the LED resistor to a 1K which should give you around 10mA through the LED.
