... Whenever I go to do one it tells me I have 11% chance of success, ... I've lost a city-state to a coup ... I've emptied my treasury re-allying them each turn ... How could they be pulling off coups that often? They obviously get much more than an 11% chance.
The probability of a successful coup is related to the amount of influence the opposing player/AI has towards the CS.
The AI seemed to have quite a lot of influence in your case. Some more and your coup-chances would have dropped to 0%.
You, on the other hand, bought back 5 CSs in a row. I guess, you reached barely the necessary influence on each of them to be allied again? Therefore the probabilities of an succesful AI coup were indeed way higher than 11%!