Goedel's theorem says (paraphrase): for every system of consistent axioms, you can always add another nontrivial axiom that will produce a consistent system. (Note that since the new axiom is not trivial, its truth value must have been indeterminate before)
When you look at it like that, it's not hard to see why this can't disprove the existence of God. God would know for all propositions and sets of axioms whether the proposition was true or false or indeterminate.
So the fallacy of this paradox is the false dichotomy of true and false. Sometimes, in a formal system, the system hasn't been defined well enough for there to be an answer.