The regulators require a certain voltage is input. Even though they output 5v, they require at least 7v or so input. (Somebody correct me if i'm wrong since im going from memory), But if you have a higher drain on the regulator, it will require an even greater input voltage. Thats why some systems will work with a lower voltage supply (like SignofZetas coregrafx), and some require a higher input (like Seldane stated with the Nintendo systems).
An alternative to the standard regulators, are "Switching" or "Buck" regulators. Instead of just wasting the extra energy as heat, they use an IC and very rapidly switch on and off to lower voltage. There are a ton of different ICs, some with set output voltages, and some with adjustable output. Pretty much all of them require a few external caps and resistors to be used.
If your interested, a company called Dimension Engineering makes a nice SUPER tiny switching regulator circuit thats designed to be a drop in replacement for standard regulators:
http://www.dimensionengineering.com/DE-SWADJ.htmI bought one im going to use in a portable snes project of mine.