Why don't you post a save-game of your attempt(s)? That way other players can check out what you do exactely. We are going to be able to help you a lot more then, because it seems that you are allready following the logical steps.
I once played a Carthago campaign on 1.5c. It was actually a very enjoyable campaign, but I had some trouble too. I think it was only H/M, but playing Carthago is a lot different then the other factions I played. Your regions are far away. I got attacked by the Ptolemaics while I was conquering Iberia and invading Italy. That learnt me that you can only focus on 1 direction at a time, because you don't have the money to maintain a lot of armies. And you definately need a decent navy. I didn't even bother to take the inland provinces, because they aren't usefull in my opinion right away. They will probably cause to much trouble to maintain public order. My intention was to take them when I wasn't at war on too many fronts so I could spare an army. Never got to that though as after I took Spain, the Gallic tribes unleashed their hordes on me.

But I remember having some public order problems in those coastal cities. And Syracuse is always a pain in the ass, whomever I play with (unless playing Syracuse

). Strangely though in my last Roman campaign, they are one of my most loyal cities. When I conquered it, I enslaved instead of the usual exterminate I do with large or huge cities, and kept a good governor in it. Syracuse is also a very good governorfactory. A lot better then Rome in my opinion.
I'm kind of tired playing RS 1.6 after looking at all those previews, but I might try Carthago again. So if you put your savegame online, I'll give it a try. Too bad I have to study for my exams though.
RJA