I think the point is you can easily remove the "deficiencies" of Euclid's proof. Basically, say: let p_1, ..., p_n be the first n primes. We can construct a new prime by examining p_1...p_n + 1. This process can be continued indefinitely.
In fact, I think the statement "this process can be continued indefinitely" is quite misleading -- to formalize this, I think you need proof by contradiction. So, the difference is the syntax used, not the actual semantics of the proof.