I've already given you a link to the info that should help you out

Anyways, I spose I'll be betatesting this as well, but here's the info anyway:
1. You can't fade to pure black, the colour is a transparency colour, thus it's not unique. I always make sure atleast one of the RGB channels has a value atleast 10 or higher (eg. 10 red, 8 green, 5 blue).
2. Even if all your colours are unique, JCS will still remove them if they are not placed somewhere in your tileset image.
That's basically what Unknown just said with a small explanation

Also, when you made the new palette, did you reload the textured background (the one with the new palette) or did you just keep the old one in the tileset and just load the new palette?
If you didn't load the new textured background then the old one would still use the colours outside of the textured background palette regardless if you changed it or not.

Explanation on 'Select Matches' in Palette Suite: (Selection --> Select Matches)
This tool will select non-unique colours in your tileset. If there are more than one of the same colour in the palette then this will pick it up. If it selects any of the entries in your textured background palette then your colours aren't unique.

Why do we need unique colours? Because JCS automatically deletes any extra values in your palette that aren't unique and automatically replaces them with lighter and darker shades of the most used colours in your tileset. (This is why when your textured background doesn't work you get holes of very light or dark colours)
Why does it do this? for the lighting special effects in Jazz2. The lighter shades are used in that beam that follows you and the darker shades are used when you reduce the ambient lighting of the level.