Make sure your History States are set to 1000 when working in Photoshop. To set your History States:

Edit -> Preferences -> Performance

On the Performance tab should be a History & Cache section. Set History States to 1000. Mine was at 20, which meant Photoshop would only save my last 20 changes. I quickly and easily filled that up with stamp, dodge and various other changes that didn't allow me to go back very far when I royally screwed up the graphic I was working on. It all worked out as I was working in layers and could just replace the layer I was working on with the original.

Bonus Pro Photosho Tip: Always work in layers