have you tried converting the backed textures to the level pallete and see how they look? Just seems like a pallete problem.

Optimism is an occupational hazard of programming: feedback is the treament.
Kent Beck