I've honestly never had this kind of trouble, not when it was first released and not when I played it on PSN a couple of months ago.

At that stage in the game I remember being roughly around level 10-13, and I had upgraded a few weapons. Making for stupidly easy battles. So go back to Lindblum, upgrade weapons and try leveling up a bit.