When trying to add a product to the cart or wishlist as a guest, I get the "Please enable cookies in your web browser to continue." page.
When I log in as a customer andtry to add a product to the cart or wishlist it works. If I log out (now I'm a guest again) I can also add products to the cart/wishlist.
I confirmed that guest and customer sessions are saved in var/session.
I tried different session cookie settings in the Magento backend, but so far that didn't change a thing.
I can reproduce this behavior on different browsers (Chrome, IE, Safari,...).
Right now I'm making little whimpering sounds of desperation, so any help is welcome... ;)