The problem is caused by updates made to the theme files for forms in recent versions of Magento.
If you are using a custom theme this means you have to manually update your theme files. Personally i had to do a time consuming 3-way manual merge between the original theme release i modified (1.1.8), the current release and my modified theme. This was to make sure i had every new change, not just this one.
I had no idea these changes had been made and think if the Magento developers can not ensure backwards compatibility they should at least put something in the release notification (in big bold letters) telling people they will need to update their themes!
anyway. The issue is with a new ‘formkey’.
Discussion on the problem and how to fix it http://www.magentocommerce.com/boards/viewthread/27447/
blueben’s post is probably the most succinct fix http://www.magentocommerce.com/boards/viewthread/27447/P30/#t97966