I think a good 16 color palette with the parallax would be more enticing than skipping the parallax, not sure about the other levels though but here is my extraction of most tiles and I think most enemies from the first level. To me it doesn't look half bad and then with some more manual work like more dithering and some color changes here and there I think it could look really good.
http://driar.se/rastanmockup/tiles_16col.png