I can think of (possibly) three ways to do this:
1) I seem to recall there being an HTML tag that's something like <BASEHREF...>; I don't know if that's deprecated, or still alive and kicking, but I think that might do what you want. However, it would skew the whole page, so it might not be what you want.
2) Use absolute URLs. Instead of something like
<a href="foo.php">Foo!</a>
Try something like
<a href="/foo.php">Foo!</a>
This should work for most cases. If, however, not everything you're linking to has an absolute URL (i.e., you want some links to change based on what directory you're in, linking to a file in that directory), try number 3.
3) You could write a snippet of code on the menu page that calculates how deep in the directory structure you are, and adds an approproate number of "../"s before each link. You would do that something like this:
for ($i = 0; $i < preg_match_all("\/", $SCRIPT_NAME, $foo); $i++) {
$linkurl = "../" . $linkurl;
}
This is just a rough sketch of the code -- you'd need to tinker a little more. Good luck!