I came across this problem while trying to test my localhost machine for adding a product to cart.
it turn out to be some sort of cookie session issue on magento.
changing session length nor disabling cookie checking does not seems to work.
its suppose to only happen on localhost testing machine, might work well on actual domain.
Setting up vhost and pointing using hosts file shall do the trick...