Initially I suspected the issue was purely related to the facebook plugin, but I then noticed the issue was reproducible for specific URLs on the site. I thought about how pages were being cached by WP Super Cache and discovered that the logged in view was being cached by WP Super Cache by searching in the supercache directory for files containing strings from the logged in view.
I then wondered if the issue was related purely to WP Super Cache but I made a test installation without the facebook plugin and the issue wasn't occurring - so I installed the facebook plugin and the issue was back.
I set about looking at how WP Super Cache was determining whether or not a user was logged in and found the function in wp-cache-phase1.php, there is a function called wp_cache_get_cookies_values(). It looks for three different cookie keys that WordPress sets when a user is logged in. I stepped through the code and found that when a user was logging in with facebook, those cookies were not being set right away. There was however a cookie that was being set at this stage, which was of the form fbs_<facebookAppID>.
I found an article that described similar issues with a facebook plugin and WP Super Cache, and in that case it was solved by writing a plugin for WP Super Cache to check for an additional cookie key. The cookie key was different to the one my facebook plugin was setting, so I adapted the code from wp_cache_get_cookies_values() in wp-cache-phase1.php, added it to a plugin which hooks to wp_cache_get_cookies_values and placed it in the WP Super Cache plugins directory. Additionally, as a comment in wp_cache_get_cookies_values() suggested, I added the cookie to test for to the conditions in the .htaccess file in the WordPress root directory.