Weird. We've tested sh404 and JFBConnect together in an earlier 3.x release, but it looks like it's time to test some more.
In the meantime, I'd recommend, in the sh404 settings where you can select how to handle each component to set it to "Skip" for JFBConnect. I don't remember the exact terminology off hand, so if you can't find the setting, let me know and we'll get to the bottom of it.
Most of the time when this happens, it's because sh404 is trying to rewrite some of the URLs that we tell Facebook to call back too. When this happens, Facebook can get upset because it's expecting one thing, and getting another. It's fixable without having to change sh404 settings, once we localize it, but until then, setting the handler to skip should work.
Please let us know how that works out!