I like the new rebel system over the old one. Personally I haven't had any issues like this, and as long as you keep an eye on things it seems to be managable. For me that means responding to issues and deciding the course of the country on that. Similar with coalitions. One can't ignore things such as internal stability and diplomacy. For me that is part of the fun of the game, and where the challenge lies.
A small country expanding rapidly will have issues if there is instability and surrounding countries that do not agree with such noble goals.
The fact that rebels spawned in the mountains and with a good general, and you cannot beat them with a mercenary army. Well, that sounds more like a strategic loss of insight, nothing personal, happens to the best of us.
As a player you forgot to account for the fact that they could retreat to the mountains.
It sounds like you wanted to use the quick autonomy button like 'fix this problem' button? Well, there is something to be said for that, perhaps, if something is not clear about that process (e.g. there is a point/ circumstances won't care if autonomy is raised.)
That region is prone to rebels though (if not in Ottoman control)? Playing around that region one of my worst fears is rebels and unstability. Due to the religion tension, and surrounding countries ready to take over Constantinople for example.