The background is changed with the style for MainMenu_RootMenuItem and MainMenu_RootMenuItemSel if you are using those styles defined in your overrides for the SolPartMenu. In each of those styles you would have a different background image or background color set.

The best option then is to write you own menu,

Or you can just use a standard HTML menu, add whatever images/links/javascript you want to your skin, the hardcoded HTML can be your menu, but you won't have access to the admin/host menus, and if you add a page that you want listed in you menu you have to add it manually.

Unfortunately those are the two solutions I know of.