Issue has been solved! Hurray!
Quite simply, javascript conflict.
Apparently I'm not alone.. All over the internet people are having issues with the Facebook Connect integration, getting the horrid error "An error has occurred. Please try again later."
I had a Wibiya Toolbar installed, which depending on the exact time of load on the page, determined whether it conflicted with Facebook Connect.
So, I put a script on each of my login pages (Anywhere the Facebook Connect is) that deactivates the Wibiya toolbar just for that page.
Problem solved.
I narrows this down when I realized that the facebook connect worked every time on my mobile devices.. The Wibiya is not activated for mobile on my website - bingo.
Hope this helps anyone who runs into this problem. If you get this error all the time, or periodically without explanation.. take a closer look at what other javascript is loading on the page, and disable the code "temporarily" one by one, to see which one is causing the conflict.
It's frustration that Facebook is so fickle.. But so useful at the same time.
- Patrick