Euclid's proof differs from what many mathematicians tell you it is. He said this:
Take any finite set of primes. (Don't assume it's the set of all primes; don't make it a proof by contradiction; don't assume it's the first $n$ primes; for example it could be $\{2,7,31\}$.)
Multiply them and add $1$. Then show (and this part was done by contradiction) that the prime factors of the resulting number are not in the finite set you started with.
Thus every finite set of primes can be extended to a larger finite set of primes.
Nothing in that argument gives you any reason to think that if you multiply the first $n$ primes and add $1$, the result is prime. That's a confusion resulting from inattentiveness to what Euclid actually wrote.
I had a joint paper with Catherine Woodgold about this in the Mathematical Intelligencer in autumn 2009:
