First of all thanks to Michelle from this list I finally found out how to easily change the navbar/navbox. Since other people on this list seem to be confused about this same point I will post how to do it again. When i get a change I will add this info somewhere to wikimedia though I'm not sure where is a good place.
Let wikiname be your wiki's name, i.e. things in the project namespace are of the form wikiname:whatever.
Go to wikiname:All system messages . This will be a very long page. Search for the entry on the navbar that you wish to change. For instance if you wanted to change 'Community Portal' search for this. You will be presented a link to change the text displayed (in the case of community portal the variable is just portal). Nearby is another link to change the url, usually the variable name you just changed-url.
I'm not sure how to add *new* links. I think you may need to go out and edit SkinPHPTal.php and xhtml...stuff.
WARNING: These changes will not take effect immediatly. After I made my changes the very next page I displayed was updated but after that the change did not show up on later pages for another hour or more. This was what caused me so much confusion.
Peter