I think that the theme should always come before gameplay.
No offense, but I've played a few dozen games that followed that theory...and they all sucked. Gameplay is the part of any game that allows the game to be
fun. With an amazing theme and crappy rules, a game will inevitably devolve into either huge arguments about the rules (in a tabletop game) or a very, very small set of 'winning' tactics being used and the rest of the game going untouched (in a computer game). Either way, the people who like the theme just end up getting upset because either way, they don't get to enjoy the theme they like so much.
Gameplay absolutely
must come first, because in a very real and literal sense, without it, the theme is just a giant game of Magic Tea Party, and people over the age of 4 don't do well at Magic Tea Party. Especially the ones that want to play so that they can
win.
All that said, theme-wise, Elements doesn't particularly pay attention to Earth's history when it makes its cards. Maxwell's Demon, historically, has nothing to do with killing creatures of any kind. Historically, very few mummies were Pharaohs. Etc. etc. Holding Crusader to a historical standard higher than any other Elements card actually
violates, rather than supporting, the theme of the game as a whole.