Zato što ti #menu nije link, IE je usran broser i dopušta hover stanje samo na linkovima. Isto tako imaš više #menu elemenata (svaka ćelij u tom izborniku) što je skroz krivo jer bi trebao imati samo jedan element sa određenim id-om na čitavoj stranici.

Code:
<div id="menu">
<a href="link">link1</a> <a href="link2">link2</a> <a href="link3">link3</a>
</div>

css: 
#menu a {
    background:....
    }
#menu a:hover {
    background: neki drugi;
    }

valjda će ti ovo pomoći da skužiš kaj ti je krivo...