Kinda remind me Advance Wars DS. There was a background menu for each character. When you finished the game you'll unlock the three backgrounds of the three characters you played the most. There is more than 20 characters, so it takes a long time to unlock everything. The good part was that you couldn't get twice the same background, I mean if your most played characters are A, B, C and your fourth one is D, normally you'll have A, B and C's background, but if you already have, say, B's background, then you'll have A, C, D.
I think this idea could be nice in Brawl. Let's say every 100 matches, you get the background of the character you played the most. You'll have to play more than 2000 matches to get everything, but you'll still have your favorites early.