I know this is really old, but I just ran into this same problem and have a different cause/solution. I installed an app from the appexchange and it was working great for me, logged in as a System Admin. I had authorized it for all users during install. Before telling staff to check it out, I used Salesforce's Login As feature to test it out. Kept getting:
You are not authorized to view this page, or the session is expired. Click Authorize to view the content.
Insufficient Privileges
You do not have the level of access necessary to perform the operation you requested. Please contact the owner of the record or your administrator if access is necessary. For more information, see Insufficient Privileges Errors.
on the URL: /setup/secur/RemoteAccessAuthorizationPage.apexp
I found no help here or anywhere until I saw a comment from someone about the Login As and OAuth. The error was being caused by me using Login As and not actually logging in as the test user. Doh!