This sounds like a battery calibration issue. I've had batteries that believed they had juice left and died before hitting 10%. I don't imagine this would be a problem with a new battery.

At minimum, I would advise running your battery until it's empty, then while leaving it off, recharge it to full. While I do not have a Desire, I imagine it indicates a full battery with a bright green light or something along those lines.

If that does not do the trick, a more indepth battery calibration guide can be found here: http://forum.xda-developers.com/showthre...

Be aware of the warning in that thread: this more indepth method may end up damaging your battery.