oye...tables!!
Well..I see a lot of unneeded code...javascript for hovers? since its just text, why not have text and change the BG color with CSS?
As for the space...its not there in FF, and I know IE has a tendency of putting spaces in when code tags have a line break inbetween them, see if that could be the case...
EDIT: Nevermind, on firefox its on the right, on internet explorer its on the left. My first guess would be mismatched widths. Just looking though, I see td spacers. Instead of using all of those extra cells, use colspan like this:
<tr>
<td colspan="10"><img src="images/navigation/spacer.gif" width="150" height="1" border="0" alt="" />
</td>
</tr>
But really I would recommend doing it over with div tags and CSS instead of tables. It's really not that much work and would be a lot easier to read/debug.
Also, I know you didn't ask about it, but the background...I might suggest tiling that on the x axis, because on my 1600px wide monitor it comes short of the right edge.