Yes, when you make large contrast increases, colors tend to get over-saturated. You could compensate for this with decreasing saturation, I made a quick attempt that I think improves the image:
1) In a levels layer, pull the black slider inwards to the histogram.
2) In a curves layer i added a rather strong S-curve.
3) In a vibrance layer I decreased overall saturation and then recovered some saturation with the vibrance slider.
Of course there's some fog left in the final image, but much of it is gone. Play around with different methods until you find something you like.