One other point in addition to the ones posted earlier - you won't be able to trade with Rebels if you've ever attacked or bribed any. That puts you in a state of war, which precludes commerce.
If all rebels on the map are eliminated, and then some reappear, you should no longer be at war with them.
Gee, I didn't remember this, all the rebels are at war after one little attack !? Or even bribed them? After all my hard spent money went to improve their province for the good of my empire ?