I had something similar to this happen to my friend's G5 tower (my old 1.8Ghsz DP w/ 6GB RAM and GeForce 5200) and a CUDA Reset fixed it.
You might have to do that as it seems a power manager issue, rather than a software/hardware issue. The fact it comes on at all, and happens in a set pattern (restart/etc..) it seems it's likely a power manage issue not telling either the monitor to turn on, or it might not be providing power to the monitor.
Same thing happened to a G5. I put a DVI (HP 1080p) monitor on the other port and it came right now. I used the ADC and the G5 would boot, but the light on the monitor was dimly lit and the screen stayed off).
btw, try with both monitors attached and see if works differently. It might be addressing the other video port on the card when it comes out of sleep/restart.
In either event, I am guessing 99% that the power manager on your Cube is corrupt.
I have never messed with a cube, so I don't know how difficult it is to get at, but you are talking to a person who knows his way around the insides of Apple and PC laptops, so while it's no stranger to dig in, I can't speak for your expertise.
you have most likely been in it before, but if not, check iFixit to find the documents. even if you have been in, they might have a better/easier way of getting to it.
It would be rather a jerk move to make it that you have to disassemble the whole stupid thing to reset the power manager. Even on a G4 tower/G5 tower all you gotta do is pull down the side/pull off the side and it's about 2 steps from opening it to resetting.
You may have to break down and do that to fix it, but afaik it fixed the issue on my friend's G5 and it hasn't happened again
oh, also if that doesn't work (don't think I read it all yet) try a reinstall, my friend's G5 wouldn't sleep right and we did all the usual (PRAM/NVRAM/etc..) and it turned out his system was corrupt and would crash silently as soon as it hit sleep and we could never wake it without shutting it off and turning it back on.
So a system reinstall might also fix it.