I have had that problem too. I just keep trying, and about the 3rd or 4th try, I usually get a match.
Here's another thread about it...
i cant get online when i press search for match it says no valid matches? please help (if already posted plz give link)
META KNIGHT definition: UBER BAD ASS!
Brawl Code: 1590-4500-0038
add me plz also pm me if you r adding me thanks! plz only add if you live in canada or the u.s
my nickname is: DOM