Which coil is firing? It kind of sounds like the left kick out, but I can't tell from the video.
Also, can you take a picture of the trough board connectors and boards themselves. Stuff like this is fairly common with Super Pins, and is usually due to failed optos and/or bad IDC connectors.

I'd start with testing MPU all of the trough switches are in the same column (#8) which is coming from J207-9.
Disconnect J207 and J209 and power the game up.
Connect an alligator clip to pin 9 on J207 then touch the other end to pins 1-9 on J209 one at a time.
You should get a single beep and the display should tell you which switch just registered.
If you get a double beep you have a problem on the MPU board.
If that test comes back good, I'll have to keep thinking about it some more...

Yakrobat OK. Well looks like the MPU is not the culprit. Could you take some pictures of the trough connectors, and the area around the trough boards. Something is obviously squirrely with the trough...

The 12v supply could be taxed by the color DMD, or there could be a weak solder connection on a repair made. The only times I've seen this type of thing happen on a super pin trough board were due to having a bad connection from the grey yellow wire on the transmit side of the trough board.
If you plug and unplug the connector with the game powered on and in test you get this behavior.
The video looks to me like the board is completely losing 12v and regaining it constantly.
I know you said your voltages all look good, but are you getting around 11.98 on the regulated, 14 something on the unregulated, and around 20 on the 18V test points?

OK, so now we're getting somewhere...
TP1 is your 12vUR and should be at about 14.8 volts. (which runs your motors and optos)
This voltage is created from your AC input from the transformer at J112 (white green wires)
and is converted to 12vdc from BR5 and smoothed by C30
Did you replace any bridges or caps when you did your basic rebuild?

TP8 is your 18vdc and should be around 19-ish volts while not under load (I think, I don't have my meter with me right now so I can't confirm on mine)
This also runs your lamp matrix and creates your 12vdc regulated (which looks fine)

Personally I'd correct the 12vUR issue first, then tackle the 18v issue next, it shouldn't cause you any issues as long as it stays above 14 volts (which is the minimum you'd need to create the 12v regulated you need I think).

Check the pin-wiki for WPC for more detailed (and professional) information.

http://www.pinwiki.com/wiki/index.php?title=Williams_WPC (it's section 6.4.2 LEDs and test points on WPC-089 Power/Driver Boards)

Yakrobat any updates?