If you are using SDK, your app must be allowed. If it's not, then there is some problem in your Salesforce settings. Go to:
Setup > Administration Setup > Manage Apps > Connected Apps and have a look at Require Users to Log In option.
Check if it's set so that the users need to log in the first time they use the app, and the permissions are maintained?
This should help.