I had the same problem and could fix it by setting the correct
web/cookie/cookie_domain
and
web/cookie/cookie_path
values in the table core_config_data.
Don't forget to clear all session and cookie data in your browser and the Magento session and cache files/data afterwards.