Working on a cloud app.  We develop software that makes calls to 3rd part REST apis (ie Facebook or Twitter) to get/put data under the user's account (using OAuth2 procedures to authorize).

In Salesforce, I created a connected app and it works great for ME.  But we tried to use an account that belonged to a different organization and that failed.  We were able to login during the OAuth2 token acquisition procedure and received back both access & refresh tokens.  However, when we ran the app using that account the token was rejected.

I did some research and it appears that I would need to package my app and have the administrator of the other organization install it.  My coworkers are sure that this is wrong and that it should work fine just like FB & Twitter.  Am I wrong?  If so, any guess why the other user's token failed? Maybe I just need to tweak the app's permissions somehow?