As KCd explains in a comment, the proof of the PNT in Hardy's time seemed to be intimately connected to the complex analytic theory of the $\zeta$-function. In fact, it was known to
be equivalent to the statement that $\zeta(s)$ has no zeroes on the half-plane $\Re s \geq 1$.
Although this equivalence may seem strange to someone unfamiliar with the subject, it is in
fact more or less straightforward.
In other words, the equivalence of PNT and the zero-freeness of $\zeta(s)$ in the region
$\Re s \geq 1$ does not lie as deep as the fact that these results are actually true.
The possibility that one could then prove PNT in a direct way, avoiding complex analysis, seemed unlikely to Hardy, since then one would also be giving a proof, avoiding complex
analysis, of the fact that the complex analytic function $\zeta(s)$ has no zero in the region $\Re s \geq 1$, which would be a peculiar state of affairs.
What added to
the air of mystery surrounding the idea of an elementary proof was the possibility of accessing the Riemann hypothesis this way. After all, if one could prove in an elementary way that
$\zeta(s)$ was zero free when $\Re s \geq 1$, perhaps the insights gained that way
might lead to a proof that $\zeta(s)$ is zero free in the region $\Re s > 1/2$ (i.e.
the Riemann hypothesis), a statement which had resisted (and continues to resist)
attack from the complex analytic perspective.
In fact, when the elementary proof of PNT was finally found, it didn't have the ramifications that Hardy anticipated (as KCd pointed out in his comment).
For a modern perspective on the elementary proof, and a comparison with the complex analytic proof, I strongly recommend Terry Tao's exposition of the prime number theorem. In this exposition,
Tao is not really concerned with elementary vs. complex analytic techniques as such, but rather with
explaining what the mathematical content of the two arguments is, in a way which makes
it easy to compare them. Studying Tao's article should help you develop a deeper sense of the mathematical content of the two arguments, and their similarities and differences.
As Tao's note explains, both arguments involve a kind of "harmonic analysis" of the primes,
but the elementary proof works primarily in "physical space" (i.e. one works directly with the prime counting function and its relatives), while the complex analytic proof works much more in "Fourier space" (i.e. one works much more with the Fourier transforms of the prime counting function and its relatives).
My understanding (derived in part from Tao's note) is that Bombieri's sieve is (at least in part) an outgrowth of the elementary proof, and it is in sieve methods that one can look to find modern versions of the type of arguments that appear in the elementary proof. (As one example, see Kevin Ford's paper On Bombieri's asymptotic sieve, which in its first two pages includes a
discussion of the relationship between certain sieving problems and the elementary proof.)
But I should note that modern analytic number theorists don't pursue sieve methods out of some desire for having "elementary" proofs. Rather, some results can be proved by $\zeta$- or $L$-function methods, and others by sieving methods; each has their strengths and weaknesses. They can be combined, or played off, one against the other. (The
Bombieri--Vinogradov theorem is an example
of a result proved by sieve methods which, as far as I understand, is stronger than what
could be proved by current $L$-function methods; indeed, it an averaged form of the
Generalized Riemann Hypothesis.)
To see how this mixing of methods is possible, I again recommend Tao's note. Looking at it should give you a sense of how, in modern number theory, the methods of the two proofs of PNT (elementary and complex analytic) are not living in different, unrelated worlds, but are just two different, but related, methods for approaching the "harmonic analysis of the primes".
What is mathematics? One answer is that mathematics is a collection of definitions, theorems, and proofs of them. But the more realistic answer is that mathematics is what mathematicians do. (And partly, that's a social activity.) Progress in mathematics consists of advancing human understanding of mathematics.
What is a proof for? Often we pretend that the reason for a proof is so that we can be sure that the result is true. But actually what mathematicians are looking for is understanding.
I encourage everyone to read the article On Proof and Progress in Mathematics by the Fields Medalist William Thurston. He says (on page 2):
The rapid advance of computers has helped dramatize this point, because computers and people are very different. For instance, when Appel and Haken completed a proof of the 4-color map theorem using a massive automatic computation, it evoked much controversy. I interpret the controversy as having little to do with doubt people had as to the veracity of the theorem or the correctness of the proof. Rather, it reflected a continuing desire for human understanding of a proof, in addition to knowledge that the theorem is true.
On a more everyday level, it is common for people first starting to grapple
with computers to make large-scale computations of things they might have
done on a smaller scale by hand. They might print out a table of the first
10,000 primes, only to find that their printout isn’t something they really
wanted after all. They discover by this kind of experience that what they
really want is usually not some collection of “answers”—what they want is
understanding.
Some people may claim that there is doubt about a proof when it has been proved by a computer, but I think human proofs have more room for error. The real issue is that (long) computer proofs (as opposed to, something simple like checking a numerical value by calculator) are hard to keep in your head.
Compare these quotes from Gian-Carlo Rota's Indiscrete Thoughts, where he describes the mathematicians' quest for understanding:
“eventually every mathematical problem is proved trivial. The quest for ultimate triviality is characteristic of the mathematical enterprise.” (p.93)
“Every mathematical theorem is eventually proved trivial. The mathematician’s ideal of truth is triviality, and the community of mathematicians will not cease its beaver-like work on a newly discovered result until it has shown to everyone’s satisfaction that all difficulties in the early proofs were spurious, and only an analytic triviality is to be found at the end of the road.” (p. 118, in The Phenomenology of Mathematical Truth)
Are there definitive proofs?
It is an article of faith among mathematicians that after a new theorem is discovered, other simpler proofs of it will be given until a definitive one is found. A cursory inspection of the history of mathematics seems to confirm the mathematician’s faith. The first proof of a great many theorems is needlessly complicated. “Nobody blames a mathematician if the first proof of a new theorem is clumsy”, said Paul Erdős. It takes a long time, from a few decades to centuries, before the facts that are hidden in the first proof are understood, as mathematicians informally say. This gradual bringing out of the significance of a new discovery takes the appearance of a succession of proofs, each one simpler than the preceding. New and simpler versions of a theorem will stop appearing when the facts are finally understood. (p.146, in The Phenomenology of Mathematical Proof).
In my opinion, there is nothing wrong with, or doubtful about, a proof that relies on computer. However, such a proof is in the intermediate stage described above, that has not yet been rendered trivial enough to be held in a mathematician's head, and thus the theorem being proved is to be considered still work in progress.
Best Answer
Simple questions often have complex answers, or no answers at all.
If you were to ask me why the sky was blue, to give a complete answer I would have to describe the heliocentric model, the earth's atmosphere, and the electromagnetic spectrum.
If you asked me how my computer connected to the internet, the answer would take a considerable amount of time to explain.
If you asked my whether there was life on other planets, I wouldn't be able to give an answer; we just don't know.
Often, it is impossible to give a simple answer to a simple question. This is true in any field you might encounter, ranging from the sciences to the humanities. And it is true in mathematics,
Mathematics allows us to formalize our questions within an axiomatic structure. It lets us ask our questions more precisely. But it in no way guarantees that the simplicity of the question would translate into simplicity of the answer.
Some other simple problems which cannot be answered simply:
The Four color theorem states that any map made up of continuous regions can be colored with 4 colors such that each region gets 1 color and no two adjacent regions get the same color. The proof is quite complex, requiring the use of a computer.
Scheinerman's conjecture is the conjecture that "every planar graph is the intersection graph of a set of line segments in the plane" (sourced from http://en.wikipedia.org/wiki/Scheinerman%27s_conjecture). However, the proof was only completed in 2009, and is fairly difficult.