Okay, I played Arabia until around 900 with the Nov 10th version.
I rapidly conquered Anatolia all the way through Constantinople, and only lost a few troops. The Byzantines were largely using archers to defend, but Constantinople had a castle with a long bowmen, so I lost a few troops there. Afterwords they collapsed, and I claimed their African cities.
Around 750 I started to have stability problems, and by 850 I had cities declaring independence. I only had one foreign contact: The Bulgars, who wouldn't give me open borders (they were orthodox, and I was Islamic).
So I think expansion stability for Arabia could be tweaked upwards, especially since they have a huge land area on the RFC-Europe map, and their UHVs are expansion related. I had a 14 cities by just expanding relatively historically through Anatolia + Constantinople and N. Africa. All my other stability categories were 3 stars, Expansion was 2 stars and dropping. Which reminds me, at least for testing purposes, you should use let us see specific stability numbers on the F2-economy screen.
There should be a at least one more independent city in N. Africa, maybe Tunis.