I had the same issue with v2.5. Please check your apache server logs. If you have SQL issue of table does not exist, just disable wooocommerce plugin then re-enable it, this will recreate the appropriate missing new SQL session tables.
This would be the case if it was broken for admin/logged in users too.
I’m not getting **any** cookies set. This is very odd, but indicative of server side caching (varnish or similar) but 123 claim this is not present.
See if you can find server errors logs and look for things such as ‘headers sent’ as this would prevent a cookie being set.
Also look in wp-config again for anything cookie related.