The Cherokee are a little over powered, especially if you are just expecting what would be normal rebels in MTW. I got my arse kicked the first time I went up against them, and I had to laugh when the next time they used my own cannon (previously captured) on me.

More unexpected than poor gaming. Just make sure you are a full stack or two when you go up against them and wipe them out quick, they seem to spawn like rabbits and I couldn't finish them off until around turn 20 - which was much later than I thought it would take.