External Power Voltage Drop

So I'm attempting my first Arduino project.

The setup is working 100% ... when powered via USB from my laptop. When plugged in via USB, I took a measurement of the 5v pin on the arduino and got 4.9 volts...HOWEVER, when I use my external power source, I can only get 3.9 volts on the 5 volt rail and that doesn't give me enough juice to kick over the relay in my project...

My external power source setup: I'm using a 12 volt battery. To keep heat down, I have a 5v switching voltage regulator (Mini DC/DC Step-Down (Buck) Converter - 5V @ 1A output [TSR12450] : ID 1065 : $14.95 : Adafruit Industries, Unique & fun DIY electronics and kits). I have verified (with multimeter) that it puts out 5v. I'm plugging it into the VIN pin...

Since I'm already regulating the voltage, should I just plug the voltage straight into the 5v pin? Will that power the Arduino? Just want to make sure I don't start plugging things in and frying them...

For anyone interested:
It's a fan controller on for the electric fan on my truck. I'm reading resistance from a thermistor and when it reaches a certain calculated temperature, it powers on a relay that then powers a fan.

Thanks in advance!

You can't use the VIN pin below 7V, the on-board regulator needs that difference.
You can either go into the 5V pin or what I like to do is buy a 9V regulator and go into VIN with 9V.

Awesome! I just plugged my regulated 5v power supply into the 5v pin and now everything works just like it does on USB and I'm getting 4.9ish volts on the output pins again.

Thanks for your help! I didn't want to just plug in and risk frying something.