In my game (Brutii: Normal) the Julii have managed to conquer most of Gaul and Spain, whilst the Scipii managed to build an empire in north Africa. Britannia also seems to be doing well and I have noticed some British provinces as far east as Northern Macedonia.

However, I agree that the AI does seem to take multiple attempts at capturing rebel cities, rarely sending a large enough force to do the job.