Esco,
I can edit these backgrounds. I personally do not think the DraculaXX ones suck, but I will concede that, on their own, they would not hold water, and require some editing. However, this is the case for all backgrounds taken from other games. The DraculaXX ones suffer in that they're in the same layer as the stalactites, so they need to be edited out, as well as having their color palette re-examined.
I encourage you to let me know what direction you are taking with regards to this, as I can probably help with the editing so that they do not look out of place and match the general style.
Also, would you be willing to compromise and create the NitM Saturn stages if there were new backgrounds and artwork for them? It seems like you have a bias against the NitM stages because 'they're ugly'... but if you're the game designer, you can reimagine these stages in a way that would improve upon them vastly. In this way you're both catering to the fans of the stages (many concede that the graphics for them would need to be improved) and would be adding some new content to the game.
New content is always good.
I have seen those backgrounds online before. I'm sure our CV Fans here can find them. If not, I can probably rip them.
EDIT:
The Spriters' Resource actually has the entire CotM Catacombs map, and has the separate layer for the tombstones highlighted.
They probably don't like if I hotlink, so here's a link to the page itself:
Spriters' Resource CotM Catacomb MapEDIT:
They also have tombstones in Harmony of Dissonance's "Approach of Deplore" (Wailing Way):
Spriters' Resource HoD Approach of Deplore