Central Air Unit not Sending Enough Power to Thermostat
This is the most common problem with the Nest.  You need to hook up a "C" wire.  

Here's the thing. Originally, thermostats were passive devices - nothing more than switches.   And so, controls were wired in a "switch loop" similar to how switches in houses were wired before current electrical code.  Power went in a functional loop: from the 24V transformer, to the thermostat, to the actuator, and back to the transformer.  

The R wire is sorta like a "hot" wire, the other wires at the thermostat are sorta like "switched hot". And just like a switch loop doesn't have or need a neutral, neither does the thermostat (the neutral would be the C wire).  

Old style dimmers and motion sensors powered themsleves by leaking a bit of power through the incandescent bulb.  That fails with efficient CFLs or LEDs.  Likewise, the Nest tries to power itself without a C wire by leaking a bit of power through the big clunky old relay that switches on the furnace, fan or A/C.  That fails with efficient relays or electronic controls. 

In this situation, you need to run a C wire, as the Nest manual discusses.  Tester101 is proposing that you may have spare wires in your thermostat cable.  

There are other ways to solve the problem, but they're starting to resemble electrical engineering.