Oh ya...
If that's a regular ol' 9v battery (little flat one like Jumper said), that isn't going to work well at all, at least not for very long.
Dropping the operating frequency of the PIC might help.
And of course, as Jumper said, put extra cap's everywhere.
Your PIC16F877A is probably brown-out resetting every time you start moving a motor (or maybe one motor or both or whatever). The smaller PICs might be a bit less sensitive to power dropoffs, or maybe they're LF versions whereas the '877A isn't an LF version.
Who knows...
One thing I do know is that the schematic shown above could use a bit of redesign to make it more reliable.