"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!
that's correct...it works even if the 12v supply is providing power via VIN as long as the usb is connected to EITHER a computer or a 5v supply.
No schematic necessary...I get it and really should have already tried that. I should have specified that I am using a capacitor on the LED side. I'll try at the supply again. Not really sure why I didn't think of that.
Also the supply is 12v 30A switching. Amperage is obviously not the issue. If it wasn't clear even powering from ONLY the 5v USB power (if memory serves something in the order of 500ma) will work just fine too.