I had a similar experience. When I first got them, they worked great in the summertime. No complaints. But they were bloody awful for me in the winter:
* Nest would, randomly, refuse to turn on AUX heat. I woke up one morning and my house was in the upper 50s (the set temperature was 68) and Nest was just sitting there trying to run the heat pump instead of turning on AUX when it wasn't keeping up. At first I thought there was something wrong with my HVAC system, but I've had two different people look my system over, on three different occasions, and found everything working properly. Nest was just refusing to turn on AUX.
The first time it happened it was in the single digits outside and Nest let my house get into the upper 50s (temperature was set at 68, and it was still trying to run the heat pump even though it was in the single freaking digits outside). I finally took Nest off the wall and manually shorted the aux heat on - I didn't want the house to get any colder while we "troubleshooted" it, and Nest was just refusing, no matter how I adjusted it, to turn the aux heat on and warm the house back up.
* Other times, it would use AUX when it doesn't need it. It was 37 outside once, and nest was burning AUX like crazy when the heat pump was having no problems keeping up. I had a nearly $400 power bill that January. Now, in fairness, it was very cold that month, but Nest using AUX when it shouldn't was a big contributor.
For awhile they wouldn't even let you set an AUX lockout lower than 35! There was a complicated "hack" you could go through that involved juggling the thermostat and the smartphone app and taking advantage of some timing flaw to set it lower. The most recent update in November or December allowed you to set a lower lockout, but the gremlin returned and Nest would be burning my AUX heat again when it was 40 outside.
How did I finally solve this? For now, until there's a better solution, I;ve set my location to somewhere 50 miles south. Really.
* They are very difficult to troubleshoot. At the time there was no way to manually turn on AUX, even to test if it's working. The only way we were able to test it is to take the thing off the wall and manually short the wires together (and, of course, it worked fine).
This is not some weird setup either. It's a standard heat pump with electric heat strips for aux heat, that's only about 5 years old. Where I live, this is the absolute most common form of heating. Because I can take the thermostat off the wall and short the wires together to turn aux on (and because I've had two different HVAC contractors check my system), I'm fairly certain the problem is not my HVAC system.
The biggest problem was, after three times of waking up to a cold house, I had a very difficult time trusting them. I had an infant in the house, and for something that I'm not supposed to have to think about, I was spending an inordinate amount of time worrying about.
So at one point I replaced one of them with a Honeywell (not the Lyric, one of the touchscreen models). And it worked fine for the rest of winter and was much less crazy to deal with, but once summer rolled around the Honeywell wouldn't turn my air conditioning on! In troubleshooting it, we found that the Honeywell was defective and wasn't putting enough voltage to activate the reversing valve. So the heat pump was still running.
So I ended up putting the Nest back on for the summer, but spent a lot of time reading the Nest forums. Apparently problems with AUX heat are SUPER common with Nests (just Google "nest aux heat" to see tons of complaints).
I'm still very wary of them. If I wake up to a cold house again, they are going right in the trash can and I'm getting another Honeywell or an ecobee3. I like being able to monitor and control from my phone or the web, but not at the cost of having to constantly worry about either my house getting too cold at night or a $400 power bill.