Um, not to be obnoxious or anything, but centering in CSS (with a block element, or any element that's set to display as block) is trivial*; you absolutely do not need to use a table unless Netscape Navigator 4 is high on your "browsers to support" list. Your navigation bar is a list of links and actions that the user is able to carry out, so a list is how it should be presented in HTML (ul or ol is up to you); you may choose to indicate its separation form the page content by making it a logical division (a div) in pre-5 (X)HTML, or as a nav element in HTML5.
Tables are for tables. If there isn't a natural row/column relationship between the cell contents, then a table is the wrong element to use. It just makes things unnecessarily hard for people who are already having a hard enough time. Every developer should, at some point, grab an evaluation copy of
Jaws to see how visually-impaired users (and machines/bots) experience their pages -- it's quite an eye-opener†.
Your markup should be semantically meaningful -- or at least as semantically meaningful as the tags and attributes allow. Remember, HTML is a language to describe the
content of a document, not its appearance. We kind of forgot about that back in the '90s for a while (we pretty much had to, since the major browsers were running off in different directions and there was no real standard). We're sorry we did that, and we've worked hard to create an environment where you don't have to do what we did anymore.
* That includes centering the bar, centering the text or contained elements withing the bar, and centering the text/images within contained elements within the bar -- both horizontally and vertically.
† In this case, there is a lot of information about the table context thrown at the user. Blind users can't see your table, so they need to be told when the row and column change (and if there's a TH that applies, what the "tag" is for that cell's data).