I'm guessing it's some floating point accuracy problem.

I managed to work around it by adding a number to the depth of my "sprites" (ie the objects that don't have to be skewed in the iso engine). My player character was always at coordinate 0,0,0 (in camera space), and it was flickering, ie sometimes it was underneath the tile he was standing on, and sometimes he was above it. If the difference between it's depth and the tile he was on was very small, the sort sometimes put them in the wrong order, but by increasing it's depth slightly, it works.

Strange though, because it worked with the normal sort method.