I had exactly the same problem at
www.grocerylighting.com. None of the suggested fixes worked for me (Wordpress3.0.1) so what I ended up doing was:
Going to Style and Edit Header and removed %pages
Opened Appearance/Editor/header.php and went to line 65. Directly under <table>
Type in your links i.e.:
<tr><td style="height:30px;">
<a href="http://www.yoursite.com"> Home</a>
<a href="http://www. yoursite.com/about/">About Us</a>
<a href="http://www. yoursite .com/contact-us/">Contact Us</a>
<a href="http://www. yoursite .com/site-map/">Site Map</a>
</td></tr>
As you can see, I changed the height and added the links. It works!