The original texture uses nearly half of the palette which most of the 32 terrain objects share, so there won't be much room for new colours. I've attached the full 113 colour palette file for the terrain (112 + transparency). If you force your new texture to remap to that palette, all objects and background etc will work perfectly.