ATMega328P clock speed increasing

I am programing an ATMega328P on a breadboard via the ArduinoISP sketch. My setup is the one found here with the 16MHz crystal:

I can burn the bootloader and haven't had any problem programming sketches. However, the sketches aren't acting correctly. When the ATMega328P is powered off of the Arduino's power rail, the Blink sketch will run fine indefinitely. However, when I switch the power rail to a 9V battery through a 7805 regulator, it will run fine for a few minutes before suddenly speeding up. It's starts off suddenly at around twice the speed, but goes up to what seems around 10 times as fast (it's hard to really tell at that speed). If I had to wager a guess, I would say it would be my decoupling capacitors. But, I've tried both 22pF ceramics and 10uF cans (all I have) with the same result. But, even that seems doubtful as there can't be too much noise on my lines. I don't think the battery would be low as it seems it would slow down were that the case. Any other possibilities I might be forgetting?

Thanks. I don't frequent the forums, but hope to join the community more now that I'm off for the summer. =)

What is bad about that circuit is that there are no decoupling capacitors at all. The capacitors on the crystal are not decoupling caps.
Add a 0.1 to 1uF ceramic cap on the power supply. If it is being run by a battery and voltage regulator you need caps on each side of the regulator a 0.1 and a 10uF on each side.
You might find that what is happening is that the board is being reset rather than speeding up. Try blinking at a diffrent pattern, say four shorts and a long to confirm this.

Sorry, I meant the decoupling capacitors on the 7805. I know the ones on the crystal aren't, although I'll admit I'm not sure they're exact purpose other than making the crystal work :stuck_out_tongue:

I would put those caps to the supply and regulator, but all I have on stock is what I ordered recently from digikey. However, after going over a few things, it looks like I'll be having to make another order anyway.

I tried a different pattern, but garnered similar results. I blinked the SOS signal (I figured it being slightly appropriate) and garnered the same results. I even changed the pull-up resistor on the reset line and the same thing happened.

It must be something with the power line. I'd check it with a multimeter if I had one (broke college student). But, maybe now is a good a time as any to invest. I might post a picture in the morning if things appear fruitless. But, it's late where I am. So, goodnight! =)