Did you put fresh batteries in the Nest? No. Because the Nest doesn't take batteries :)
So that raises a question. How does Nest power itself? It has a lithium battery (like a phone) but that has to be replenished somehow.
The answer is, Nest depends on the fact that thermostat wiring is in series with the furnace relay. Power flows
-----R wire--------------------------- THERMOSTAT
/ /
/ /
/ /
TRANSFORMER -------W wire-------
\ /
------C wire----- FURNACE RELAY
Now, on most furnaces, the furnace relay is a physical relay. They require a certain amount of current flow to "pick up" or actuate. If current is too little, they will not pick up.
So if the thermostat leaked a small amount of current through the relay, it should not actuate. So the Nest takes advantage of that. It leaks that small amount of current - which typically will not actuate the relay on most furnaces - and uses that current flow to power itself. This is the same way old style dimmers work.
There are two ways this can blow up. #1 the relay may not be able to flow enough current to power the Nest. #2 that small current may be enough to actuate the relay and turn the furnace on. #2 is your problem.
Two ways to solve this.
Put a dummy load across the relay so current has a second path
-----R wire--------------------------- THERMOSTAT
/ /
/ ---DUMMY LOAD-- /
/ / \ /
TRANSFORMER / >-----W wire---------
\ / /
----+-C wire----- FURNACE RELAY
Now current splits and follows 2 paths: through the dummy and also through the furnace relay. Smart sizing of the dummy load will divert enough current to stop the relay from actuating. On most furnaces.
Several companies make appropriate "dummy loads" for use with the Nest.
Add a "C" wire to the Nest
If none of these options work, Nest has the provision to take power directly off the transformer, by tapping the transformer via an extra wire: the "C" wire.
-----R wire--------------------------- THERMOSTAT
/ / /
/ -------------C wire----------------- /
/ / /
TRANSFORMER / -------W wire------------
\ / /
----+-C wire----- FURNACE RELAY
We haven't seen the sheath of your thermostat cable; typically furnace installers use larger cable than you immediately need and simply wrap the unneeded wires around the thermostat cable sheath. So you may have 1-3 more wires in that cable that are unused. If so, this is fairly easy.
A "wire multiplexer"
They make fairly complex powered gadgets which allow you to cram 5 wires worth of signal (R, W, G, Y, C) over 4 wires (or even 3). However they are a mighty octopus to wire, and prone to creating very difficult-to-troubleshoot problems, so I disrecommend them until the "dummy load" option has been exhausted.