I just noticed I duplicated a color by accident in my textured background image, which I might've noticed earlier if I didn't rush...

You can tell how good your palette is by taking an in-game screenshot with F12 while in 8-bit mode, and then examing the palette of the newly created pcx file findable in your JJ2 folder. Any color that doesn't get used by any tile will be replaced by some random color. I'm guessing you might have used colors from JJ2's sprite palette and/or your textured background doesn't have enough colors.

I also recently noticed something regarding using indexes 208-239 for the textured background. The textured background tiles must contain no more than 30 colors, and these colors must be placed within 209-238. However, there still must be a complete gradient from 208 to 239. This means you would have to specifically place the two colors for 208 and 239 (and any other colors from the gradient if they were left unused) in some tile outside of the textured background (this incidently explains the purpose of the "dizz suxx" tile in the Colon 2 tileset).

Edit: If an 8-bit background looks bad, it's usually because the maker of the tileset didn't put enough effort into the palette.