Despite this, I believe everything would have worked if not my units started routing much sooner than I had expected - I thought I still had plenty of time to bring my still fresh Lancers on the left into the enemy's flank, but no; they ran. To buy myself some time, I sent my general into a depleted unit of Berbers chasing my BI's. 40 fresh Byz. Lancers against 26 tired Camels sounds like a pretty easy fight, especially when you achieve a perfect charge in their flank. But no, a few seconds later my Lancers were losing badly
Can you give me the stats on Byzantine Lancers (I assume they are either from VI or some mod, I only have vanilla)? Since you said you brought lighter type of cavalry to the desert, I'm going to assume that they're not that beefy. If that's true, then your defeat isn't surprising in the slightest. Camels kick horse butt, I learned it the easy way only last week myself (ran some Bedouins into some Ghulam or Mamluk cavalry for the heck of it in a quick battle and was surprised to see that the enemy was ripped apart). I ran a few custom battle rounds of Bedouins agains Feudal Knights in the desert on flat ground and the average result was almost 30 camels left with 5-10 knights running away. Even up a slight slope there were 20 camels left (though they were wavering for a second there). Now Berber camels are weaker, but unless Lancers are on par with knights you still had it coming for you :P Camels mop the floor with any sort of lighter cavalry.

In fact, I had a major battle where I successfully used camels just yesterday. I unexpectedly had to fend off about 1200Mongols led by at most 2 star general on Khazar arid flat ground as Turks with 8 star general and both to my dismay and exitement found myself with all the wrong types of troops: only two units of foot archers (Futuwwas), three Saracen Infantry, two Ghazi Infantry and loads of various cavalry and cavalry archers instead of foot soldiers, as well as Naphta Throwers which I had never used before... With even something totally basic like half Murabitin Infantry and half whatever kind of foot archers it would've been a breeze - but also would've been boring. I was, however, lucky enough to find myself with camels :) And I was lucky enough to find the enemy with only 4 units of heavy cavalry. I didn't fight very well at all (in the replay I discovered that one of my Saracen infantry was facing the enemy with their backs -_- of course they were the only one to recieve a charge by heavy cavalry). But with a huge valor advantage I managed to crush the first wave anyway and in the second there were only like 8 units of Steppe Cavalry left. I was growing pretty impatient so I didn't hesitate sending my handful of camels (2 full units and 3 halved ones) straight against the 8 fresh units of Steppe cavalry and they slaughtered the enemy completely. I don't think I lost more than 3 camels in that one. Well camels didn't manage to actually CATCH them once they were routing so they went Benny Hill on me but I chased them over the border eventually.