  (Abridged) A phase of strong interacting matter with deconfined quarks is
expected in the core of massive neutron stars. If this deconfinement phase
transition is of the first order then it will be triggered by the nucleation of
a critical size drop of the stable quark phase in the metastable hadronic
phase. Within these circumstances it has been shown that cold pure hadronic
compact stars above a threshold value of their gravitational mass are
metastable with respect to the "decay" to quark stars (compact stars made at
least in part of quark matter). This stellar conversion process liberates a
huge amount of energy, and it could be the energy source of some of the long
GRBs. The main goal of the present work is to establish whether a newborn
hadronic star (proto-hadronic star) could survive the early stages of its
evolution without "decaying" to a quark star. To this aim, we study the
nucleation process of quark matter in hot beta-stable hadronic matter, with and
without trapped neutrinos. We calculate and compare the nucleation rate and the
nucleation time due to thermal and quantum nucleation mechanisms. We compute
the crossover temperature above which thermal nucleation dominates the finite
temperature quantum nucleation mechanism. We next discuss the consequences of
quark matter nucleation for the physics and the evolution of proto-neutron
stars. We introduce the new concept of limiting conversion temperature and
critical mass M_cr for proto-hadronic stars, and we show that proto-hadronic
stars with a mass M < M_cr could survive the early stages of their evolution
without decaying to a quark star. We extend the concept of maximum mass of a
"neutron star" with respect to the classical one introduced by Oppenheimer &
Volkoff to account for the existence of two distinct families of compact stars
(hadronic stars and quark stars) as predicted by the present scenario.
