Lindebaum's Lemma seemingly inconsistent with Gödel's incompleteness theorem? 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.
