I have a similar battery charging problem with a recently purchased Clip+. I bought the 8GB version with fw 01.02.15 three weeks ago and immediately charged it overnight. I took the unit off the charge and made sure it was turned off. Two days later I took it to the gym and there was no charge as soon as I turned it on. I plugged it and charged it and seemed to have no problems after that. But once again this week I used it to listen to FM radio, then plugged it in after showing low charge. The next morning I found that the unit had not charged at all, but instead had continued to discharge. I power cycled the player and then continued charging. This time the unit got charged. In both instances of failing to charge I had observed the charging icon in action so there was some positive indication that the charger was working.
I have another 4GB Clip+ running firmware 01.02.13 that has not had this problem, so I don’t know if this charging problem is related to fw 01.02.15, new unit break-in (a theory discussed a while back in the forums), or my unit is a flaky one.