What I was trying to explain is that the last picture doesn't have that specific problem and you wouldn't need to waste much time finding out what you'd have to change in your workflow.
In the following picture, I applied heavy denoising while trying to keep most of the detail:
http://i.imgur.com/9LvGGYr.jpgIt's not a perfect example and it has different states than yours. I just want to point out that, even with this denoising strength, it doesn't get that kind of problem and neither does your last picture, even if I clean it up. These are the places with more noticeable color loss in "Main Street":
http://imgur.com/a/P9bauI've had similar problems in the past because of incorrect colorspace conversion, bit depth and compression so I thought I should tell you about this while you're still working on the backgrounds, in case you're not aware of it. In my pov, there's no trade-off regarding this problem, there's only doing it right or wrong. If you think it's fine the way it is and people like it, that's all that matters.