I'm assuming that the "Search Engine Friendly URLs" is enabled in all cases? It doesn't really matter either way, but if it's disabled, the use rewriting setting doesn't do much anyways.
Either way, if rewriting is causing you problems, it's likely that you haven't renamed the htaccess.txt to .htaccess on your server (if you're using Apache). If you did rename that and are still getting that error, then the only other thing to try is to insert index.php into the url and see if that works. By that, I mean, if your SEF URL that isn't working looks like:
yoursite.com/good-looking/sef-url
to
yoursite.com/index.php/good-looking/sef-url
If that last URL works, then it means the .htaccess file hasn't been renamed or the .htaccess file is being ignored by your server for some reason.
Definitely not JFBConnect related, but we'll help how we can.
Thanks, and good luck,
Alex