http://en.wikipedia.org/wiki/Mamertines - I know it's only Wikipedia, but the article shows that they appealed to Pyrrhus, Rome, and Carthage for protection. Ultimately they ended up with the Romans, so would it be worth giving Messana Roman culture, particularly as they were of Italian descent?
I'm still keen on Rhegium being Greek to increase the chances of it revolting? Or is it just going to be a rebel settlement? I guess you'd also need to consider the effect the culture would have on the AOR troops available too?