My Nikon D80 started having the same Low Battery issue with a fully charged battery few months after I purchased it in June 2007 and it got much worse in the past month.
I missed shots because I had to turn off and turn on the camera to get around this very annoying issue. I am considering buying another battery to see if it is a battery problem.

Other than this fault, the camera works well.