Have you tried turn-based? Looking at the statistics, there are literally 0 tables of Medina in real time, but there are currently 74 of them in turn-based, so you might have slightly more luck there.
In fact, as I am typing this, 3 tables are currently waiting for additional players to start. Two in "2 moves per day", and one is "1 move every 2 days".
(Using "Manual" mode instead of "Automatic" to see the tables)