I loaded up this plugin and it worked fine for me.
Make sure you went to Dashboard > Settings > NoFollow ExtLink, and set “Apply nofollow to Menu” = checked, then click “Save Changes”.
If it still doesn’t work, its possible some other software on your site is causing a conflict. Deactivate other plugins and switch to the default theme and test. If it works now, reactivate one-by-one and check to try to identify which other item is causing the problem.
You may get a better answer from the plugin’s support forum. It looks as though the plugin author does generally respond.
https://www.ads-software.com/support/plugin/nofollow-for-external-link
