An easy example of a non-constructive proof without an obvious "fix"? I wanted to give an easy example of a non-constructive proof, or, more precisely, of a proof which states that an object exists, but gives no obvious recipe to create/find it.
Euclid's proof of the infinitude of primes came to mind, however there is an obvious way to "fix" it: just try all the numbers between the biggest prime and the constructed number, and you'll find a prime in a finite number of steps.
Are there good examples of simple non-constructive proofs which would require a substantial change to be made constructive? (Or better yet, can't be made constructive at all).

There's a classic example from point-set topology. The statement is this: suppose $X$ is a topological space and $Y \subseteq X$ is such that for all $y \in Y$ there exists an open set $U$ such that $y \in U$ and $U \subseteq Y$. Then $Y$ is open.
Most introductory textbooks will tacitly use the axiom of choice along the following lines. For each $y$, choose $U_y$ satisfying the above properties. Then $Y = \bigcup_{y \in Y} U_y$ is a union of open sets, so $Y$ is open.
In fact the axiom of choice is not needed at all. Instead, let $S$ be the set of open sets contained in $Y$ and simply note that $\bigcup_{U \in S} U = Y$.
