If the new battery behaves like the old one (and the new one was a genuine replacement and not worn out itself) then the problem has to be somewhere in the device itself.

What I'd do is try to find someone near you who has a N900 and swap batteries with her, to see which one would have the problems.