I need a little help...

Your doing it right, it should work just fine. You see, unlike most hex changes, a palette change will NOT occur for a character if you already have Shadow recruited in one of those instances. To see the changes you will have to play before you have recruited him, or the game will just think it's still at palette #4. In other words, changing a characters assigned overworld palette will only take effect when the event in question is called. If this is not the problem, you are changing the wrong bytes, but I'm fairly confident it's what I'm thinking.