It is usually thought that a single equation of state (EoS) model "correctly" represents cores of all compact stars. Here we emphasize that two families of compact stars, viz., neutron stars and strange stars, can coexist in nature, and that neutron stars can get converted to strange stars through the nucleation process of quark matter in the stellar center. From our fully general relativistic numerical computations of the structures of fast-spinning compact stars, known as millisecond pulsars, we find that such a stellar conversion causes a simultaneous spin-up and decrease in gravitational mass of these stars. This is a new type of millisecond pulsar evolution through a new mechanism, which gives rise to relatively lower mass compact stars with higher spin rates. This could have an implication for the observed mass and spin distributions of millisecond pulsars. Such a stellar conversion can also rescue some massive, spin-supported millisecond pulsars from collapsing into black holes. Besides, we extend the concept of critical mass for the neutron star sequence to the case of fast-spinning neutron stars, and point out that neutron star EoS models cannot be ruled out by the stellar mass measurement alone. Finally, we emphasize the additional complexity for constraining EoS models, for example, by stellar radius measurements using X-ray observations, if two families of compact stars coexist.