Once upon a time, in the faraway kingdom of Michigan State University, I was making my tileset, minding my own business, when suddenly, the textured background's 2nd and 3rd darkest shades turned fuzzy white. (The textured background fades to pure black). So I thought to myself, "Self, the stuff you just added to the tileset must have contained the same colors as the textured background, thus eliminating it from the background palette." Unfortunately, when I changed all the colors of the new tiles to "safe" colors, it still didn't help the background. I made sure that in JCS, the darker background colors were not interpreted as "black", so I'm stumped. Disguuuuuiiiiiiiiiiiisssssssse!

Does Palsuite find any "Select Matches" in your textured background gradient?
Do you have at least one other tile with all the textured background colors somewhere in the tileset?

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.

Hmm... well, I tried changing the background fade color, and it had no effect. Even when I put in crazy numbers like R:0, G:255, B:10. I noticed that it helped when I changed the water blocks for some reason. The colors were still off, but they changed from whitish to greyish. Then, I changed the water blocks again, and it changed to really bright white. It's weird, because the water blocks do not contain only shades of blue and grey, while the background contains only shades of green (with a very slight touch of blue).