It seems like bribing won't work against other Roman factions. I tried on a number of towns some containing only captains and the option wasn't there. It has worked on my other alllies though and they never went hostile either. Looks like I'll have to go to civil war to get those provinces.