The probabilistic method is typically used to show that the probability of some random object having a certain property is non-zero, but doesn't exhibit any examples. It does guarantee that a "repeat-until-success" algorithm will eventually terminate, but does not give an upper bound on the runtime. So unless the probability of a property holding is substantial, an existence proof by the probabilistic method makes a very poor algorithm.
In point of fact, probabilistic algorithms aren't actually constructive existence proofs, so much as they are algorithms to produce constructive existence proofs. The output is an object of the sort which it was meant to prove the existence of; but the fact that it will eventually yield one ("there will exist an iteration in which it yields an example — except with probability zero...") is not enough to be constructive; it will only be satisfactory to someone who already accepts that non-zero-probability-without-construction suffices for existence. Conversely, if you do have a good bound on the run-time, then there's in principle no excuse not to run it in order to actually produce an example. A good probabilistic algorithm still isn't a constructive proof, but a good plan to obtain a constructive proof.
Note that this idea, that a randomized algorithm is a proof strategy (as opposed to a proof in itself) to demonstrate an existential quantification, is not unlike the idea that induction is a good proof strategy to show a universal quantification (over the natural numbers). This analogy may seem compelling, as induction is essentially the heart of recursion as a computational technique. (For any positive integer $n$, if you want to decide whether $n^2$ is a sum of the consecutive odd numbers preceding $2n+1$, you can reduce this to investigating whether $(n-1)^2$ is a sum of the consecutive odd numbers preceding $2n-1$, and so forth.) Induction is essentially an algorithmic proof-strategy which we have elevated to a theorem, allowing us to have the knowledge without explicitly computing it each time. However, induction is accepted constructively because it is already an axiom(-scheme) of Peano arithmetic, and one which is independent of the other axioms. By contrast, there is no rule of inference or axiom which allows the probabilistic method to prove existence constructively, or to constructively prove that probabilistic algorithms produce existence proofs, or anything along these lines. You simply cannot prove that there are examples of a class of object from the fact that there is a probabilistic algorithm to construct it, unless you already accept that proposition, either as an axiom, or from other premises.
Of course, one might adopt a philosophical position intermediate to constructivism and the classical approach to existence, and say that what one wants is not constructions per se but construction-schema which are allowed to fail with any probability less than one; that would make any probabilistic construction "schematic", if not completely constructive. Where one wishes to draw the line, to say that they find an existence proof "satisfactory", ultimately depends on how much intuition (in a non-philosophical sense) they wish to gain from proofs.
