Hi Alex,
It sounds like your add-on consists of spreadsheet custom functions. My understanding is that custom functions only get run when the user has authorized the add-on, and simply calling a custom function from a spreadsheet formula does not trigger the authorization dialog box.
The easiest solution is probably to add a menu item like Add-ons > Alex's add-on > Start. The function that gets run by the menu item does not need to do anything but could open an info sidebar or something like that. The point is that the user can choose the menu item to run a function interactively, which is enough to trigger the authorization flow. If no authorization is required, nothing happens, but if some scopes are required, the authorization dialog box gets shown.
It is likely that your add-on requires at least some scopes. You can check that in Script editor > File > Project properties > Scopes. To make the authorization dialog box less scary, remember to include the @onlycurrentdoc pragma in a Javadoc comment someplace in your script.
Cheers --Hyde