Lindenbaum's Lemma: Any consistent first order theory $K$ has a consistent complete extension.
First Incompleteness Theorem: Any effectively generated theory capable of expressing elementary arithmetic cannot be both consistent and complete.
If the hypothesis of the First Incompleteness Theorem holds for a theory $K$, why doesn't an application of Lindenbaum then yield a contradiction?
What you've shown, as Asaf points out, is that Goedel's incompleteness theorem implies that $PA$ has no computable completion.
This addresses your question completely. However, at this point it's reasonable to ask, "How complicated must a completion of $PA$ be?"
It turns out the answer to this question is extremely well-understood (google "PA degree"). One interesting and very important aspect of this is the following. Let $0'$ be the set of all (indices for) computer programs that halt. It's easy to see that $0'$ can be used to compute a completion of $PA$ (or any computably axiomatizable theory), since the question "Is $\varphi$ consistent with $T$?" can be phrased as "Does the machine which searches for proofs of "0=1" from the axioms $T+\varphi$ ever halt?" So there will be some completion of $PA$ which is no more complicated than $0'$.
However, it turns out we can do substantially better. There is a certain class of sets called "low" - low sets are not computable, but are "close to" computable in a precise sense. Roughly speaking, it is no harder to tell if a low theory is consistent than it is to tell if a computable theory is consistent. By the Low Basis Theorem, every computably axiomatizable theory actually has a low completion!
So even though we can't always get computable completions of computable theories, we can always get "not too incomputable" completions.
Why is the completion of an effectively generated theory stays an effectively generated theory?
In fact, this shows that it doesn't.
