The arena matching system is completely random, that's to be expected.
One possible fix to this is to not make it completely random. Instead, deck with more plays (relative to the deck age, else old deck will not get any play) will get reduced match percentage, and deck with fewer plays will get more chance.
It bugged me too, but not so much.