While it's true that other plugins can interfere, sometimes this means that you setup your Facebook Application incorrectly. It's easy to fix though.
First, go here: http://www.facebook.com/developers/apps.php. There you will find your Facebook Application. Click the "Edit Settings" link on it. From the settings pages, you'll want to look at the "Web Site" tab.
The basic underlying problem here is that you have the wrong values on this page. The "Site URL" needs to be the *exact URL of your site*. And this does mean *exact*. Whatever shows up in the Browser URL bar is what you *MUST* put here. It's amazing how many people think their website has a "www" in it when it doesn't, for example. Or how people just use capital letters wherever the heck they please. These things *DO* matter, the values must be EXACTLY correct.
Possible multisite problem:
If you are using multisite with domain mapping, then you may have enabled the "Remote Login" and/or "Redirect Admin pages" options. These are fundamentally incompatible with Facebook. The way Facebook works is that it expects the domain name you're currently on to match whatever is set in the App itself. So if your admin side of things uses a different domain name than the actual site itself uses, then it's just not going to work at all.
There is no possible way to workaround this. Don't use those two options in the Domain Mapping plugin.
One of those two issues is generally the problem.