Games are, generally, made in an iterative fashion. Stuff builds upon and informs other stuff. However, what is the orinal thing to be built upon. The question put above is utterly a false dichotomy. You can absolutely be lucky enough to get both, nor is it the case that those are the only two possibilities, for example, one could get inspired to try a particular graphical style.
An example of where you could get both is in the case of an actual sequel or a spiritual sequel. Another case would often be in simulations such as sports games, although that still leaves some of the mechanics up in the air. For example, one could imagine a sports game where you only played one teammate. That’s possible if you’re simulating football, but not if you’re making a sequel to FIFA.
Still the false dichotomy above is a useful question to ask. I also feel that it answers itself by the asking. Your gut reaction is, I would suggest, the right one since it is a matter that changes depending on the person asking it. In my mind, theme can come far easier than mechanics, yet theme can be a trapping alley – if your proposed mechanic is poor you can test it and then discard it, if your proposed theme does not lend itself to good mechanics when do you know – for example my match-making Emma game has run into mechanic after mechanic that simply doesn’t work.
Starting with theme is tempting, it really is. But starting with mechanics is more enjoyable.