The other issue at hand might also be where in the file your flash is compared to where your actual menu is, I've ran into issues with a menu or any other content stacking correctly in IE6 when flash is involved. For some odd reason, I always have to put the menu outside the actual wrapping div that the flash is situated in.
For example:
* Doesn't work right in IE
<div id="wrap">
<div id="menu"><ul><li></li></ul></div>
<div id="flash"><flash movie params></div>
</div>
* works better
<div id="wrap">
<div id="menu"><ul><li></li></ul></div>
<div id="flashcont"><div id="flash><flash movie params></div></div>
</div>
The trick is not just z-index and wmode="transparent" - sometimes in IE, it is also native stacking order.
I would take everyone's ideas and create a hybrid to get this to work. The swfObject is real nice, but it is used before the page renders, so if your thinking about using it to build out your flash dynamically (post-page load), it is fairly complicated to have it do the right thing unless your just sending new flashvars data to the flash object and updating via DOM scripting. With that aside it is weird that the wmode="transparent" didn't work, that usually fixes this issue no questions asked.
I hope this helps.
Scott Haines
San Francisco Bay Area Web Design