I had a similar issue on a site that I am working on at the moment.
The categories get the text styling from CategoriesList in skin1.css. The A:Link etc styles control the colours of the links. However, if you want the hyperlinks to show against different backgrounds then best to set a class to the <a href> of each link.
ie
Link