In order to properly handle sprite priority, you need to do things a bit differently.
Instead of drawing sprites in the order 63->0 and drawing lower numbered sprites on top of higher numbered ones, draw them 0->63 but only allow each pixel on the screen to be occupied by *one* sprite.
The important bit here is that sprites drawn behind the background are still treated as being drawn, so a higher numbered sprite will NOT be rendered in that particular location.
Note that all of this is per-pixel, and transparent sprite pixels do not count.
P.S. If you don't get this note, let me know and I'll write you another.