Blender 2.75 to 2.76 When adding an object I can't find the tool menu now!? Add (Vertices / Depth etc)
Click the + icon at the bottom of the region.
When the redo menu is resized to nothing, it is hidden and the + button for re-showing it appears: