I'll look into this some more. Are you playing on the web or the windows exe (they actually have slightly different matchmaking algos, although this shouldn't happen in either). Part of the issue could also be that since I've updated the version in the latest patch, it can only match against teams created with that new version. As the game is played more, the pool of matches will get bigger.
The relics I have already planned out are mostly about boosting effects in-combat. I'd like to make sets of relics that enhance all of the major gameplay strategies (tall scaling, wide scaling, summoning, death effects, sniping), as well as that add new elements. In addition to the shop cost scaling relics in now, I'll either be adding relics and/or possibly other minions that scale the stats of minions in the shop. I also haven't thought this totally through yet, but I have an idea to make "magic items" that are available in the relic selection but equip on a specific minion.
I'd also like to add Curses, which act like negative Relics, or possibly have both positive and negative effects. I'm not sure exactly how or when these will get handed out though.