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.
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.
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 acceptance proof "satisfactory", ultimately depends on how much intuition (in a non-philosophical sense) they wish to gain from proofs.