I figured it out Like I said, I DID try all the options including "Show color on title bar". It DID NOT work, like I said, why would I lie ?
However solution is to change color AFTER enabling "show color on title bar". Thats it. When I was having problem, I just enabled option, see it didn't help, and disable it again, since I didn't like solid colors on metro apps.
Anyways, thanks for your help, I wouldn't figure it out if you didn't point to that option, so I started playing with it again