Do you want to handle it tactically or strategically?

Tactically:

Most of the advice you've received above is spot on. The traditional roman strengths are those pila against unarmored foes and the tacticable speed of their swordsman to hold with one group while flanking with another. Adjusting to their specific army composition is also important.

Strategically:

Perhaps they're tough to beat because of the morale benefit of a high-star leader? If so, a couple of your best agents slipping some aresenic in his ale might do you more good than a half-dozen units of hired bastarnae. Especially if you attack the same turn the poor fellow accidentally falls down a flight of stairs...4 times.

Divide and conquer! Send in solid forces in 5 or 6 stacks, all of them positioned in good defensive spots that are temptingly close to his army. He'll go for one, and then at least two forces cut in behind to take the towns. You may lose a couple of battles, but they lose their settlements and their faction is caput. Pin and flank is not limited to the battlemap.

He might even split forces, creating easily "digestible" chunks.