If you are using relative links to the pages then if the menu is on a page in a subdirectory it will not link to the pages properly. The ways to get around this are like you have noted, having two separate menus, one for the admin and one for the public.
Another way to get around this is to add the menu into a template file (.dwt.php). When the menu is part of a template the paths will adjust accordingly for the pages derived from that template.
Yet another way to do this would be to make all of the links absolute links that start with the /. This way it would not matter where the link was clicked on, it would go to the same page.