Arduino circuit/breadboard not working at higher voltage?

Sounds like strange voltage regulator behavior. The rails should be at 5V almost regardless of the input voltage. The regulator probably has some minimum voltage it will work at but 7.2 volts should be more then sufficient.