Override Adminimal Menu styles on frontend?

I'm trying to figure out how to theme the Adminimal Menu. As default, every hover state is a shade of blue - and we want to change it to maroon (#660000). I've written override styles into a stylesheet that I am including through template.php, and it works when I am not in the frontend. For instance, if I right-click on "Dashboard" and open it in a new tab, all of my styles are applied to the menu. But if I click the Home icon to go back to the frontend, the default blue colors are back. It doesn't look like the stylesheet is loaded at all. If I click one of the menu links and it opens in the overlay, the overlay DOES have my styles - just not the menu.