Having a hint in the form of a newspaper headline would be awesome:
It could be Blatant: "Newest Legacy seeks justice for her Father's death on Mars, Baron Blade in hiding." (or whatever would be appropriate)
Or a series of less blatant Headlines: "Is Baron Blade on Mars?" "Freedom 5 to Mars, "Baron Blade must be stopped" "Newest Legacy seeks Justice for Father's death."
Just putting a headline like that after each match would be cool.
If they don't want it in the post-match sequence you could unlock a new headline, and have a little place to go look and the headlines would be organised by what promo they were giving you clues about.
I think hat would be agreat feature to add, and it could work through promo's in a specific order, giving hints until that one is unlocked, then start giving clues for the next one.
This would be great for later on too, when someone picks up the game and there are a bunch of promo cards to unlock, it would feel more organic.
Or there could be a mix, like after defeating Omnitron get a hint about fighting Voss, and then one about ships in the sky, or a military memo/plan to take out both ships at the same time. That kind of stuff could be really cool, and almost creeate a bit of storyline for new players to play through if they get the game after multiple expansions come out. If they don't figure it out after a bit give them a more blunt hint that pretty well lays out how to unlock it.
Coudl even add some dialogue explaining the promo, like you unlock Mad Bomber and he gives a little speil about taking vengeance on the city while the heroes are away, then show the unlock.
The promo challenges offer a great way to teach the story of the Multiverse, this time it was geared for thsoe who already know a lot of it to figure out how to recreate the story, but for new players telling the story through the game might be a lot more fun, and create a better bond with players.