I would definately suggest levelling up (mark-hunting always helps, plus you sometimes get good items earlier).

Another strong possibility is that your gambits might not be set up adequately. Check for those.

Don't rely on your quickenings. I usually save them to the end, when certain bosses have near-death stat-boosters you gotta worry about. Try to come up with a strategy that works, and if you can't, I would definately level up.

edit: Oh yeah, I thought Cid was an asshole in this game. Although technically he's a good guy. Kind of.