Edits:
The red background bricks are quite awesome as is.
Wasn't to keen on some of your colour choices (still far better than the colours in Castlevania
). The cyan tree trunks and red-purple stalagmites and stalactite in particular.
Reused palettes more. Same palette for foreground and background bricks.
Cleaned up the rock texture and increased contrast by making use of black.
Removed the common floor blocks from the ceiling to maintain their purity of purpose and added some variation.