Here are a few places that you could get inspiration from:
Note the multi-color boxes which match what your boss was wanting. Along with that, take a look at the Tutorials link on the main navigation bar:
When you hover over its submenu items the background of each menu item changes to the color of the corresponding box on the page.
This menu is similar to yours except that it's active page has an active lighter blue tab color. This could work very well in your scheme and be really easy to implement.
This is simliar to the Blue Tabbed Menu above, but this isn't a tab panel effect, it's simply an active item lighter background color. Also, very easy to implement.