Try out the SCSS syntax (or LESS), might warm you up to it a bit more.
In the end I find that if I organize my CSS well, changing things like colors really isn't such a big deal. Like you say. Find/Replace.
Oh well. Either it will pass as a fad or I will one day be forced into the light.
In the situations where a designer provided .psds for me to transform into html/css, no I haven't had to modify anything. But then, the iteration on the design happens with the other guy, and he does it in photoshop. If a change happens, he just sends me the new asset images, and I just replace them in the repo.
The times where I'm the one doing the design work, I end up switching things up a lot. This is because I don't do my design work in photoshop, but rather in the browser with actual html/css. So even while I'm iterating on something by myself (before having even shown the client anything), I'll switch colors up constantly trying to get something I'm okay with.
I strongly advocate giving the SCSS version a try. It's straight-up CSS with all the things that should have been there in the first place.
Rather than trying to remember a previous hex, or looking it up, you can think ok, this should be the darker highlight colour - and as you say, looking later you know which colour that is.
It's not just colours - a good example is a clearfix. Rather than add it to the markup, you can add it via css, and of course if you change it, you change it once.
Personally, while I do try to take advantage of all the features of LESS, I think the biggest thing is the ability to define macros (utilizing mixins or functions). Never again do I need to write multiple rules for one style (-moz-foo, -webkit-foo, and foo) or need to remember the complicated argument order (defining gradients is vastly different between all of them).
The cost is in introducing a compile step, but the benefit is that your stylesheet becomes easy to write, easy to read, easy to modify.
The math behind layouts can also be set using variables reducing a lot of headaches while the client wants 'the left column could be a bit wider'.
I agree that it requires a lot more coding discipline than plain 'ol CSS. So much to the extent that one would be tempted to abandon it. But like all good layers of abstractions, it reduces a lot of effort in the future.