Mike,
When I saw it has ok brightness, it refers to that in a normal lit room the message is barely readible but if the lights are off, it looks pretty good. I have a 7 LED arm swinging "floating display" clock that is bright in light or darkness AS WELL AS the MK123 scrolling clock I mentioned earlier that looks good in normal light and low light settings. This is what made me think it used new high rated MCD LEDs.
All of the supply voltages have been powered from my SX protoboards power which is from a 7.5 vdc p/s 1A into the boards 5vdc regulator.
If we go with this approach of a new higher voltage supply, then the logic chips should be powered from the SX protoboard 5vdc power and ONLY the anode FETS would receive Vcc (12v, 13.8v, etc.. at 3 A, 5 A etc...) and the ground would be common to both. However, I also think as Wilf suggested, the use of 2200 uF decoupling caps and 0.1 uF too by each chips (Vcc / Vdd / Vss) and Gnd.
You also state that this new power supply would provide a variable 5 - 9 v for the display. I thought that you said that 5 v is not enough. A bit confusing.