The highlight of Konami's Rebirth line has been its arrangements of their classic 8 and 16-bit tunes in the style of their arcade games circa the early 90s. A few months ago they released an album that had the full soundtracks for Castlevania and Contra Rebirth, which seemed redundant considering music rips had been circulating around for months. (Buying both games together is also cheaper than buying the CD itself - Japanese CD prices are still absurd.) But they did feature two tracks, dubbed "Another Medley"s, with two bonus songs each.
So technically the Castlevania Rebirth game is based on the first Gameboy game, The Castlevania Adventure. That game was terrible, but at least it had an awesome soundtrack. Sadly, the Rebirth game features absolutely none of the music from it. (It did feature a track from its sequel, Belmont's Revenge, which was quite welcome.) This medley makes up for that venial sin by including Battle of the Holy, the first stage theme from Castlevania Adventure. The second song is Lost Painting, from Symphony of the Night. It is a bit strange to here a song essentially downgraded to FM synth, but it still sounds quite classy. They really should've ditched the fifth billionth remix of Vampire Killer for this Battle of the Holy theme, but I'm not sure where Lost Painting would fit in this arcade-style game - it doesn't even really work as an ending theme.
The theme on the Contra medley is the first level theme from Contra Force, which is strange considering it was never released in Japan. (It was tentatively developed under the title Arkhound.) The character select screen in Contra Rebirth is also taken from Contra Force. The second theme is the ending from the Gameboy game, Operation C. That game was comprised almost entirely of remixes from other Contra titles, except for this ending, and the stage 2 theme, which also ended up in Contra Rebirth, for the level with the robot ostriches. If they really wanted to go obscure they should've done a remix from C: The Contra Adventure, the not-so-great (but not terribly abysmal, contrary to popular opinion) European-developed PSOne game, which actually had some great music.
Before Konami released their own official version, amazing internet remixer Otobeya did his own version, also in the style of their arcade music. See which one you like better!
His webpage is a must visit, as it includes dozens upon dozens of MP3s of classic video game music redone on other synths. There's tons of Gradius and Castlevania in there. I rather like the Ys 6 and Origin songs done on an MSX, or Metroid's Brinstar theme on a Master System, or Final Fantasy III (FC)'s battle theme as done on the SNES. The coup de grace is the My Neighbor Totoro theme done in the style of a Romancing SaGa battle theme.