1 - Open your BDC and click on your application.
2 - Now you should be at a page that provides application information. In the middle of page you will see a link "Manage Permissions" Click it!
3 - The Manage Permissions page. Click "Add Users/Groupts" link button.
4 - At this point you can enter the desired user. check the permissions usually Execute and Select in client enough. If I may suggest, add domainNam\domain users which will give the broadest reach. You can always change this later.
5 - One final thing or it will not work. Check the new user now shown on Manage Permissions List checkbox and click on "Copy all permissions to decendets" This is important.
Okay, now login as user you wish to test and checkout the results. If you already had the browser open with the error close the browser completely and open it again.
Assuming that the user in question already has access to site otherwise that has to be done first.
Good luck!