First off, is all your equipment equipped? I know I played FF1 for some time before I realized I had to equip all my nice weapons.

I'm not sure what else it could be, but level 31 for the fire cave seems like extreme overkill - usually the game is beatable by level 25 or so (I'm not sure about DoS things though). That also takes away the most generall FF1 advice - "just level up more", which is usually effective .