My money's on "you don't have all the characters". I'm guessing you're missing Mr. Game & Watch, Mewtwo, or Falco. If you do have all characters, you'll get a message/achievement saying something to that effect. And there's a thing in Data somewhere that shows all the messages you got, so you can see if you do have all 25.
I forget, if you don't beat a Challenger upon meeting them for the first time, do you have to fulfill the alternate requirement to get another chance at unlocking them, or does it constantly re-challenge you? Because it'd suck to lose both times and then have no chance of ever unlocking the character again. Which probably isn't the case. But it's just a fear I had ever since the first game.
I mean, will you seriously get challenged by that one character if you go past the "number of Vs. Matches" count and keep playing Vs. matches? It's like "Hey Bill, you try to beat him this time. Then after this, Final Destination again. Final Destination, the stage, not the movie! Geez Bill, get it together."