What are you doing when you kill the Tonberries? Are you killing them with physical attack, GFs, Card, or Devour. If you are using Card or Devour (I'm positive about the first and pretty sure about the second) then that kill doesn't count. You must actually see the Tonberry fall down and die to count as a kill. I made this mistake once while trying not to level up through the game. I forgot that they don't give you EXP, so I kept carding them, because it's faster and I was on a time limit because I wasn't getting Odin. So I carded like 25 and nothing. And then I realized my error, and I started killing them, and 20 later I got the Toberry King. And I don't know why, but I've played this game many many times, and every single time I've played this game it's has always been 20 Tonberries to get the Tonberry King.

My strategy for killing Tonberries involves a three Micro Missiles from Quistis and then a finishing blow from someone else.