I don't know if you're still searching for an answer but I think your question about submission to Facebook App Center was right.
I was having the same problem and my app wasn't submitted to Facebook as I was only using "standard" permissions (public_profile & user_friends doesn't require Facebook review). I thought that maybe submitting the app for review (only the "App Details" part) may help so I tested a simple request just before submitting and it still wasn't working. I submitted my app to Facebook (just the "App Details" part) in order to be listed in the App Center. Just after review and that my app has been accepted, I ran again a simple request and now everything seems to be working just fine. An app request opened on Android launch the Play Store if the app isn't installed or directly launch the app otherwise.
I can't say if it's a general rule because I can't find any documentation that support this idea but for me that makes sense (as the app is not listed on the app center and the Facebook app on the device cannot find any information about your application).
Hope this helps.