Sorry I just noticed it was the NES palette after posting
. That brown was clashing with the other colors of the background anyway. I cannot think of a suggestion in NES colors other than black like eishiya said. You could also make all the other colors lighter to make room for one of the NES darks, but that would take the focus out of your characters.
However, how set are you in using exclusively NES colors? Please don't take this as an intrusion on your art choices, but, as an example, your game seems quite appealing to my retro tastes, and I certainly wouldn't be turned away if you took liberties with the colors. Perhaps even using a whole alternate NES palette to be harmonious, like those more desaturated NTSC options of modern emulators, I choose them over the "default" one anyday. NES colors wouldn't even look like those we can now see in clear displays. I remember that my tube tv from childhood was way over-saturated and warm by default, and my neighboor's one was much less vivid while still warm and the colors looked much more interesting on his tv set than on my. I think Aseprite has NES NTSC built in if ever wish to give it a try.