Couple of options.
One is a repeating background image on the entire menu (repeating if this is a solid semi-trans colour). So, a PNG with an alpha layer. PNGs with alpha layers are larger in filesize than those without, but you can get away with a small image who tiles (make the number of pixels a multiple of 8 horizontally and 4 vertically). If the solid (non-opaque) colour is set as the background colour in the image editor's pallete (where you usually have a foreground colour and a background colour), then background-colour will be set as part of the image's data (even if there isn't an actual background colour on the image). This means IE6, who otherwise does not do well with alpha-trans PNGs, will at least still show the correct solid colour in your menu. If you care about IE6.
I like this idea best because it's more cross-browser than the others, though it has the disadvantage of not allowing you a proper contrast background colour set in CSS for those not loading images.
Option 2: rgba()
This is not supported by IE6 or 7, I think 8 does support but not sure. This is a newer CSS setting that allows you to specify not only a colour but also an opacity IN the colour, so long as the colour is set in RGB form. Sucks, someone must've been in love with that one.
Anyway, you could set a solid colour for non-supporting browsers, then set rgba().
I think that was how it went. Since IE and other older browsers don't recognise rgba(), they ignore that rule and so it shouldn't override the first, solid version.
Remember if you have two copies of your menu, you've got two menus. Think of the accessibility sadpandas you'd get with that : )