-Try to make a BG color scheme that's either a fair bit lighter or darker than the FG. For instance, a lot of the hills in Mario games are lighter than the ground tiles. Lightening up the BG rocks would help in this case.
-Different scroll rates for BG layers help if you aren't already doing them.
-Avoid objects similar to the FG showing up in the BG, such as a couple of the ledges you have.
-Avoid any black in the BG (which it looks like you're doing).
Contrary to what you say, a lot of the graphics here are quite nice, especially the player and the BG rock shading.