Haven't seen this issue in a while, but pretty sure I know the problem. This may get too technical for you, but I'll try to explain the best I can. Your server is likely 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, your site is likely 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.
You can check if I'm correct about this by going to the System Info area of Joomla and then in the PHP Settings, search for "suhosin" and look for the encrypt cookie setting (or something similar).
If so, that's definitely the problem. 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" and that it needs to be disabled.
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. Really hope that helps!
Good luck,
Alex