Okay, I've always stuck by the rule that after killing 80 enemies, your limits level up. (For example, Cloud killing 80 gets him from Cross-slash to Blade Beam and Climhazzard-Meteorain).
I just escaped from Midgar in Disc I, and Cloud just got Blade Beam. And I'm pretty sure I haven't had him kill 80 or more enemies. Previously, I didn't get Blade Beam until Mt. Nibel, and I had him kill way more than 80. What's the real deal behind gaining limit breaks?