Sometimes things are split up in the games code for whatever reason, and don't appear in your hex editor exactly as you would think. For example, a palette I was recently searching for was something like 00 0F 16 05, but actually never appeared like that in the hex editor. It was just 0F 16 05. So, ya kind of just have to try different things to find exactly what you are searching for.
As far as finding the hex value but it doesn't actually change it, just because you find the combination you were searching for, doesn't mean that is actually the code that represents the palette (or whatever else) you may have been searching for. It just happens that the hex you were searching for is the same as some other data in the game.
Trial and error. If you change some hex values and it doesn't do what you thought it would, change it back and try to find the next occurrence of those values in your hex editor.