I had a similar problem. In my case, I had not created a hash key using my signing key. I just had the one hash key created using the debug.keystore default signing key.
As soon as i created a hash key using my app release signing key, that problem was sorted out. If you haven’t already done this, create a new hash key using your signing key (for uploading on the market) and add that to your app’s facebook control panel.
Hope this helps.