Facebook Connect Breaks when 3rd Party Cookies Disabled

I have a website that uses Facebook Connect to authenticate users:

http://alltrails.com

Users have been reporting that they are getting into a strange redirect loop where they are logged out immediately after logging in. We found that this is happening for anyone who has disabled accepting of 3rd party cookies in Firefox which seems to be a larger enough group of people to cause some major problems.

I've dome some research and none of the suggested fixes have work. Setting the facebook cookie fbs_<your_app_id> manually on successful login doesn't work, nor does adding a P3P header CP="IDC DSP COR ADM DEVi TAIi PSA PSD IVAi IVDi CONi H开发者_JS百科IS OUR IND CNT" to our site.

Any ideas on a work around so users with 3rd party cookies disabled can actually login successfully via Facebook Connect?