You can try putting your Flash object into opaque window mode (wmode = 'opaque'), but because of the Iframe, I still expect some inconsistency.
http://www.communitymx.com/content/article.cfm?cid=e5141
You could also try coupling this with what's known as an "Iframe shim". It's definitely a hackish work-around, but one that Google themselves have used, sooo... take that as you will.
http://www.oratransplant.nl/2007/10/26/using-iframe-shim-to-partly-cover-a-java-applet/
iframe shimming or ie6 (and below) select z-index bug
http://www.google.com/search?q=iframe+shim
Good luck :) @Vili might still have the right idea with just hiding the Iframe when your menu opens. This is certainly the lowest level, and should probably happen for any browsers that don't support these other "fixes" (hacks).
(BTW, you can forget Z-Index helping on any platform or browser. Iframes and Flash both exist on macro-layers above the normal document flow. A DIV will never show in front of either without some finagling).