Actually, all the tiles that would be need to be changed for my idea (minus the Castle 1 Night warp tiles which weren't included in your set anyway) are there in the image I first posted. And even if you're only using MSPaint, you wouldn't need to redraw any pixels or use any color replacing tool. You could've use TilesetPal along with resaving the image without a palette, but I don't want to get into that right now.

Here's what would be my proposed palette as seen through palette events:



Or with a few rows rearranged:



And with either of those palettes, theoretically a background such as the following could still be possible:



You're probably going need a tile that contains the entire palette to make sure everything works. And just so you know, I used the sprite colors from Castle 1 so that the stain-glass windows would still look the same. I hope you have still have a version of your set before you did any color reduction for your convenience. But anyway, you're free to try whatever you want.