It does NOT need to be plugged into a computer but if it's not plugged into the USB in some manner
I assume it's plugged into a power supply, if not the computer? The other end of the USB cable isn't dangling loose, is it?
I normally use a robust 12v power supply
"Robust" is relative...
Try adding a capacitor (maybe 1000uF minimum) across the 12V power supply.
If that doesn't help, stick a diode in series to the Arduino (but not to the lights) and put the capacitor on the Arduino-side of the diode (to ground). The capacitor will hold-up the voltage if it glitches-down temporarily, and the diode will insure that the capacitor only discharges into the Arduino, not the lights.
...I apologize for describing a circuit in words, but I don't have time to make a schematic at the moment. I hate it when people do that!