Arduino and Servo randomly shut off on battery power

Okay, so this is my first large-ish arduino project, and it requires an external power supply. What I'm using is a 7.4 V 1600 mAh airsoft battery, connected to a 6 V voltage regulator, which goes off to power the arduino through Vin along with a servo. The problem is: every so often (first one is after about 30 seconds of operation, then they get more and more frequent), the servo will stop moving, loose all torque, and the built in led on pin 13 will shut off... but the power led won't. After one or two seconds, everything resumes normal operation. Why is this?
I speculated that the voltage regulator was eating up too much current as heat, causing a brown out, as a remedy, I tried holding it to an old CPU heatsink, and that seemed like it might have helped, but it still didn't completely stop it.
What should I do?

Okay! I've figured it out, after hours of finniking. But if anyone else has this problem, here's what I did: instead of using the voltage regulator to power the arduino and the servo, I instead had it power just the servo, and used the arduinos built in regulator to drop my batteries 7.4 V to it's 5. This seepms to have solved all my problems. I can only hope it will continue to work when I add the other 3 servos.

That's interesting, but I wonder if that was really your problem.

Maybe not, but based on my… 3… minutes of self taught electrical engineer training, I believe the problem was that the Arduino minimum possible operating voltage is 6 V, and my voltage regulator has a output voltage minimum of 5.75, so while it was outputting a full 6, everything was dandy, but when it fell to its minimum, the problems arose. If I could get my hands on a multimeter, I'd be able to prove this, but as of now, that theory is all I've got.

connected to a 6 V voltage regulator

What type of regulator is this? If it is a 7806 chip then it is probably rated for 1a max, which may be less than what the servo draws when starting.

NTE962, on http://www.nteinc.com/specs/900to999/pdf/nte962.pdf it claims it can both deliver output in excess of one ampere, and that the output current it 500mA to 1 A. So that seems to be contradicting.... also, as I will be running 4 servos, will I need 4 voltage regulators...?

also, as I will be running 4 servos, will I need 4 voltage regulators...?

One per servo would be a start.

If I could get my hands on a multimeter

Yeah, you really need to do that to work with this stuff....