I'd like to add to API-Beast's comment: Using the same palette isn't a bad thing. Using different colours can make the characters (and other interactive entities) feel like they're not actually in the world. However, using the same balance of colours/values is a bad idea. Even if you're using the same palette, the characters should be using more contrasting colour combinations than the background.
A good example of what I mean is Final Fantasy Adventure for the Gameboy:
It's limited to black, white, and two greys. The background uses all four of those colours, and yet the characters stand out quite well. Why is that? It's because the background uses mostly white and the light grey, and uses the dark colours sparingly, while the characters do the opposite - they're black with some grey, and only a little white (and they use a black outline for those things that can't otherwise be dark). You can apply this idea to larger palettes as well (but remember to take hue into account as well, not just value).