Yes, although in my experience the most significant benefit is sorting not on texture per se, but on texture size. (So rendering all 256x256, then all 512x512). In principle, the fewer state changes, the better.
That said, I guess there is some worst case scenario where you cause lots of overdraw. Experiments for your particular case may be necessary.