Which version of SOTN would be the better one to play? The PSP one from this deal, or the XBL one?
I've never played it before. The last Castlevania game I played was Super Castlevania IV.
Depends if you want it portable or not. I'd opt for the PSP version for 2 reasons: 1) portable; 2) looks better (sharper) on the smaller screen.
Either way, SotN is one of the best 2D games ever (...and much better than any of the DS versions IMHO, especially b/c of the inverted castle secret), and you need to play it if you haven't already.