By default photoshop is set to have just one undo, Ctrl+Z only works once. To change this you need to edit the keyboard shortcuts. Go to Edit/Keyboard Shortcuts. Set Shortcuts For: to Application Menus and open the Edit shortcut list.
This is what it looks like by default. Ctrl+Z needs to be assigned to Step Backward instead of Undo/Redo.
Assign Ctrl+Z to Step Backward and click the Accept button. This will Remove the shortcut from Undo/Redo while assigning it to Step Backward.
The Keyboard Shortcuts window should look like this when you are done. Ctrl+Z can now be used to step back as many times as the History States are set in Photoshop’s preferences. If you are working with a Wacom tablet or Cintiq you should assign one of the express keys or pen switches to Input Ctrl+Z.