in most cases, you would be correct... but the that really depends on how you theme actually creates the links or menus. The current version of the plugin cannot open links in a new window if the theme just calls the permalink and places it in an href attribute of an anchor tag, as there is nothing that can check it after it is created that way (usually this is the case for featured items, slider slides, etc.)
For it to open in a new window, it must have been generated by a function that returns the entire link, like in the menus, or page lists, etc. That is always the biggest misconception about that functionality not working.
The next version, due out in a few days, will have some jQuery functionality with it, that will allow the plugin to check ANY link on the page, including those in the content, and add the appropriate new window attribute, as well as the rel=nofollow attribute when needed.
Look for the new version soon. It will probably solve all of your issues.