Andy,
Can you check if there is already a user on your site with the Facebook user's email address? If so, that's the problem. You can also use the "Automatically link users by email" setting to skip that check on our part and make an automatic connection between the Joomla and Facebook user.
Hope that helps explain,
Alex