Sorry for the delays. We've been doing some research and some tests on your site. The result is that we've likely determined the issue, but will need your hosting provider to help solve it.
Your server is using the SUHOSIN PHP security suite. We use this too, and it's a great set of tools for hardening your site against a wide range of attacks. However, it's configured to encrypt cookies before sending them to the user's browser, and then, of course, decrypting the values that are sent from the user back to your site. Since Facebook is actually setting the cookie for your domain, it has no means of encrypting the cookie properly. Therefore, when your site tries to read the users cookie, it first 'decrypts' it, which actually just scrambles the value.
We've done quite a few tests on your site to set cookies, and see the resulting value. If we do it (through your server), the cookie is gibberish. However, the Facebook cookie is always legible. So we're pretty confident this is the cause.
You may be able to disable the encryption using a .htaccess file and adding the following line:
php_flag suhosin.cookie.encrypt Off
Otherwise, your hosting provider may need to set it up in the vhosts.conf file (if that's how the server works). Either way, they should know best, but let them know the setting name of "suhosin.cookie.encrypt".
Good luck, and definitely let us know your results. This is a new issue to us, and we're curious how it will work out.