Supposedly you can get Lucina by playing 40 matches-- I did, and I got a chance, and I lost to her. In old versions of the game, it would keep giving you more chances to beat the newly unlockable character after each successive match (the 41st, the 42nd, etc)....but I'm at like 80 matches now and have not gotten another chance to unlock her. The internet says beating classic mode with marth on standard difficulty unlocks her, too, but....I got ROB instead.
What can I do? This is for the 3DS, not Wii U.