Post titles change style depending on categories (wp 3.3.2)

Hello,
I’m struggling for about 3-4 days and I cannot figure it out!
I have for example two categories: paintings & magazines. I would like when I’m adding a post and change category to paintings the post title has red color and when I change to magazines, the post title has green color.

I have tried many tutorials, like for example these:
http://justintadlock.com/archives/2008/12/06/creating-single-post-templates-in-wordpress

http://wordpresshero.com/tricks/different-single-post-pages-in-wordpress.html/

and some plugins and many forumulas but none worked.

I’m using theme called maximum:
http://fearlessflyer.com/themes/maximum/

and I don’t even have a template option from admin -> posts -> categories -> edit .. so that I can change it permanently from there.

Is it my template or something else is goind on? I have read that some people with wordpress 3 and above the above tutorials have worked for them and some others say that they don’t work due to Template Hierarchy, etc.

I will give up if you guys don’t have any idea.

Thank you all and I would like to thank especially Esmi that he had helped me in the past.