Why do you dismiss the game of chess so lightly?
OK, maybe chess is not sufficiently complex
but I think it is a reasonable hunch to say
every proof in any finite axiomatic system can be reduced
to finding the correct move in some position in the game of GO.
If this seems outlandish
don't forget that Conway has shown
that his game of LIFE is sufficiently complex
that it can produce a Turing machine.
I don't think its a matter of complexity, but one of "proof" and knowing all the statements within the system using the system itself, the validity of an axiomatic system to be "complete" in that sense. Something beyond the system is needed, and then the incompleteness is encountered again.
I can't really illustrate using your chess analogy effectively off the top of my head, maybe someone else will.
It's certainly possible for a game to be complex enough to embed mathematics in. If so, however, the interest in the game would be due primarily to the fact that you can embed mathematics in it, not for the game itself. (Well, the game might be interesting or entertaining as a technical problem anyway, but you had asked why Gödel's incompleteness theorem is considered profound. I don't think any analysis of chess or Go or whatever could be considered profound -- again, unless you could embed something of independent interest in it, in which case that would be the reason for considering the result to be profound.)
Incidentally, I don't think that Go is complex enough for what you're suggesting, since it's played on a finite board, unlike Conway's game of life. (I would guess that Go might be PSPACE-complete, which is pretty complicated, but nowhere near complicated enough to embed a universal Turing machine in.)