Yes that is exactly correct. I would suggest using VBA to find the palette and then just changing the colors accordingly. I personally like the more blue underwater anyways To my understanding, in the game only 16 palettes are available for use in the tiles. Another way you could do this is to change a palette that is not being used. I did this to add in a lava section to one of my maps. In this case, I used palette 7 to change some of the unused pink to red. Otherwise just stick to using palette 6 which is all blues (Icefall Cave uses this palette I believe)
Well, that thread is much too confusing for me with all the questions and answers. In answer to your question, yes. I used the ruby tileset for underwater but added onto Tileset 38 (The ice tiles) using Palette 8. Here is what my tiles look like so far. Basically just went into paint and used the right clock trick to change the colors on the tiles from Ruby.