Probably handle it similarly to how Chrome handles an extension asking for new permissions. It disables the add-on and gives the user a small non-intrusive notification on the options menu. Opening the notification notified the user about the change in permissions and asks them if they want to re-enable the add-on or remove it from Chrome.