Untested (on iPhone) but try setting margin-left:auto; margin-right:auto; on the top level (outermost) menu ul. You might also need to give it a width - try your 800px suggestion, or whatever width accommodates the buttons nicely.
If that doesn't work, also try setting text-align:center; on the menu container div.
OK - just back on a PC. This does actually work, so you would set it up like this (assuming that everything else is the default CSS);
<div id="smoothmenu1" class="ddsmoothmenu">
<ul style="width:500px; margin-right:auto; margin-left:auto;">
<li><a href="http://www.dynamicdrive.com">Item 1</a></li>
... etc ...
With the DD demo menu, a width of about 500px accomodates the existing buttons (roughly their combined width - edit this to the width of your own once you've decided on your own button names/fonts).
The reason why you'd need to define a width on the ul in this case is that a ul is a block level element, which means that it always spans a 100% width. And you can't center something that is already 100% wide - the auto left and right margins have no effect because the edges are already flush to the left and right edge of the screen/container.
If you give the ul a fixed width (eg. 500px) the auto left and right margin now CAN take effect and align the smaller 500px child element in the center of the parent container - the #smoothmenu1 div, which is also a block level element, and again spanning 100% width of the screen (no need to define a width on that unless you want to reduce the width of background-bar)
Doing it this way will float the buttons in the middle of the bar and allow the bar to span the full width of the any size screen.
I'm glad you've already found a workaround but I just wanted to clear the logic up for you so you can move away from the table solution if you wish.