When you have the highest current draw, at what voltage level is the Vcc dropping?
I believe, since your batteries are old, it drops below or goes very near the required voltage for the regulator to work under spec.
From my experience, 9V batteries don't mix well with voltage regulators, unless you use them with LDO 3.3V perhaps, but that's an assumption.
I had used two 9V in parallel and a 6V regulator to get sufficient power output when I had built this DIY line follower robot:
http://myrobots.gr/robots.html ("babycloud") Otherwise it wouldn't have worked as expected.
Of course now I know better, and I would have used a AA battery pack, which is also my recommendation for your project, since it will make it more reliable in the long run.
George :-)