It sounds as if your customer login/checkout login/cart page doesn't have a form key. Inside the form tag on each of these templates, you need to have the following:
<input name="form_key" type="hidden" value="<?php echo Mage::getSingleton('core/session')->getFormKey() ?>" />
Edit: Here is more info at the bottom of the latest patch: http://magento.com/security/patches/supee-6788-technical-details