I've had the same result. As the Bruti, the senate wanted me to make the Dacians a protectorate. They were down to their final city (Lovovisce, I think, in any event it was landlocked), it had one general and two units of falxmen as garrison, I had a full 20 unit army (general, 1st cohort, 9 legionary cohorts, 2 roman cav, 2 legionary cav, 1 wardog, 4 archer auxiliae) outside the walls, and another pretty much identical army within the borders. I got the "Our freedom is precious to us" speech, no matter what I demanded or offered, so I just killed them.