As far as Coppermine goes there is plenty of information to create a custom theme on these boards and in the faq. Creating a theme beyond the basics of what files to edit, and where they go, theres not a whole lot we can create a tutorial for. The main part of the theme, is your own creativity and ability to put that creativity to work with all of the web development tools you have under your belt.
Themes are based in PHP and HTML, but they can include Flash, CSS, inline-style, Java, you name it, theres probably a way you can incorporate it.
The actual problem that you are encountering doesn't really have to do with Coppermine Themeing per'se. Most of the coppermine themes use CSS to establish the color schemes and a significant portion of the "style" information that browsers renders. If you want to be effective in editing/creating themes, there are plenty of CSS tutorials available. Just Google it. Explaining CSS would be a forum in and of itself, and you can find forums already dedicated to it.
http://www.htmldog.com/guides/cssbeginner/ Looks like a good reference.
CSS is not simple, it can be quite complex as there is not necessarily a 1 to 1 relation to everything you style in CSS.
Selectors can select parents or children, or the item itself. Some properties are inheritable, some aren't. You can style elements multiple times, last writer wins. You will see examples of all of that if you look through the css of the default themes.
It's very likely that whatever color you are changing on an element, is changed by a more specific element assigment elsewhere in the css.
When dealing with CSS I've found the best troubleshooting tools being the Web Tool Bar's for developers.
Internet Explorer:
Web Accessibility Toolbar (Creative Commons License)
Mozilla Firefox:
Web Developer Extension (GPL)