I don't think this has anything to do with how new the phone is or whether or not you let the battery go through a full charge/discharge cycle. I got a brand new One V and I had this problem on the second day I owned it. I let the battery discharge all the way and then charge back to 100% uninterrupted, phone was fine for a day or two, then I started having the problem again.
Since rooting and clearing the Dalvik cache I haven't seen the problem again, but it's only been four days. No idea if this is a permanent fix, but clearing the Dalvik cache never hurt anything...