Yeah, that's what I've been doing, but they don't seem enough. So you'd have to make your own palette for large pixel overs.Hmm. See, for the pixel-overs, I was using the palettes of the in-game sprites.
For mine, I use a little of both. What I do, to give them a realistic, sort of "cinematic" look to them (It's a little hard to describe without showing you some and I don't want to put my pictures into someone else's thread) is to take the colors directly from the image I'm pixeling-over (Not sure what the present-tense of pixel-over is XD) and compare it to the sprite to get it as close as possible to the basic color. However, this shade, when layered with highlights and darker shades, will look much less cartoony than the colors of the actual sprites, since it was taken from the artwork itself. Also, more shades indeed makes them look more natural, so if you would rather use the sprite's colors, you would need to create some. As a rule, for a pixel-over as large as your Kingdra is, you'll want to have at least two more shades than the sprite has. The smaller your pixel-over or sprite, the less shades it will need to have to appear natural, since there's less space. But the more shades you have with anything of any size will appear more realistic. It just takes more shades the larger your sprite is.
Now for a few comments! I like the trainers. If they were made from scratch, then good for you, because I can't even draw believable-looking humans.
The banner (or whatever it is) looks like it would be really good! Don't scrap it! At least finish it, even if you won't use it. I'd like to see the finished product.
Keep up the good work and make more pixel-overs! They're hands-down, my favorite of all the spriting arts and I love seeing other people do them. Yours are very nice. Great job.