I have had exactly this problem. Here's my experience and resolution.
My Legend is about 6 months old and worked fine (charging fully for about the first 3 months). I'm not sure if it is linked but I bought one of those stands which charges the phone and keeps the phone upright so that you can use it as a bedside clock. Not sure if having the screen on all night did something to the phone but I think the charging problem may have started around the time that I started using this charger.
Having eliminated any charger / cable issues by using a variety of alternatives I then bought a new battery to see if it was the original battery at fault. No change.
I then did a factor reset. No Change.
I then contacted Vodafone UK customer services who sent me another new battery free of charge. No Change.
I then contacted HTC customer services via one their online chat service. The guy on the other end had never experienced this problem. He thought it might due to one of the Apps causing a problem. I did another factory reset and didn't reload any of the Apps. No Change.
I then contacted Vodafone UK again, they confirmed that the phone was still under warranty and 24hrs later a new phone was delivered to my house and I handed the original phone to the courier to be returned to Vodafone. I was hugely impressed with this as I didn't demand a new phone, they just offered it.
New phone works fine, charges all the way to 100% with the LED indicator going green.
I won't be using that bedside table charger again just to be on the safe side.
Hope the above tale helps.