Oh, well how much detail do you need for the tiles, because IIRC, the tileset for Cavestory is HUGE, so you probably won't be needing every tile converted.
EDIT: I just pulled a screenshot of the first cave. Are you talking about the actual square tiles or the background tiles?
EDIT2:I just grabbed a small chunk of tiles and worked with it. It's weird, it seems that these tiles have a 5 color palette. If you want, I can probably try and dither the 5th color, but then that would take much longer to do all the tiles.
EDIT3: Had a little extra time so I felt like making a little mockup screen for Cavestory. YES