Team Ninja has acknowledged how difficult it is to find matches. They added this to the Information Bar on the Main Menu:
"Trouble with matching for solo ranked fights? Try raising the min. opponent strength or switching the match type to tag. Sorry for the inconvenience. We are working to address this issue."
I don't understand how raising the minimum opponent strength will help. Wouldn't that narrow down the possible matches to even less players? Also, that's weird that apparently this issue is affecting mostly Solo. It's definitely true that I find Tag matches way more often than Solo. Is it really that there are that many more people playing Tag, or is there something bugged about the way this game searches for Solo matches? Either way, I really wish this game gave you the option to search for both Solo and Tag at the same time.