First, StevieB: Which battery was replaced, the main / external battery or the PRAM / internal battery?
And $39.95 for the internal battery?
Second, liz: It sounds like you need a new battery. The same thing happened with my PB. Replacing the battery took care of the problem. I ordered a replacement battery from Amazon for under $30. It arrived about 50% charged, and when it was inserted in the PB, the power connector turned orange (charging).
The old, failed battery had one status light (of the five) that was flashing rapidly.