I've been wanting to do a similar "Double Dragon" style beat-em up style and run into the same problem. The only way I can think to reduce framerate issues is to use a combination of layers for static objects and the dynamic layering stuff only for objects that can change their Y (players and enemies usually). Generally both the background and "ground" can just be a flat image on the bottom layer.
If you find a better solution, please share it!