Well, I tried out the whole magic level theory and...nothing, still the same low damage. Even when I maxed out everything (and I mean everything, HP and MP, Magic levels + experience, stats, weapon levels) and even de-equipped everything, it still did paltry damage. I'm beginning to think that there's some unknown value going on here, most likely something along the lines of no. of enemies killed, no of times magic used in battle etc. This might explain why Ryu seemed to get high damage Ultima through spell levels. It wasn't the spell levels that were the factor but the amount of times he used magic.