why not using halfbright mode ? With well choosed colors you could get 32 colors for your sprites and 32 for hinderground.
But well, maybe i don't see some problem that would come with that mode, i rarely used it myself.. er well, never in fact i think
But seeing how well Black Crypt looked in this mode, this maybe could be an option (?).