Since the total mass-energy for the neutrino presumably does not change when a neutrino changes lepton flavor, though the mass is different, what compensates for the gain or loss of mass? Does the propagation speed of the neutrino change?
There are a couple of misconceptions here.
Finally, note that all the neutrinos we can interact with have energies measures in MeVs or GeVs, and all the mass states are understood to be less than 1 eV, so all neutrinos are ultra-relativistic: they move a the speed of light for nearly all practical purposes. (The exception here is the hope of comparing the arrival time of the neutrino and light wave-fronts from distant supernovae.
The reason neutrino oscillations are confusing to those students who think carefully about them is partially because of the history of how the neutrinos were discovered.
Originally, it was thought that the neutrinos were massless and so the flavor eigenstates were the only states that existed. Then the neutrinos were named electron neutrino $\nu_e$, muon neutrino $\nu_\mu$ and tau neutrino $\nu_\tau$. But these were not the mass eigenstates. We usually call the mass eigenstates $\nu_1$, $\nu_2$, $\nu_3$.
So rather than think of the situation as one involving the transmission of a single neutrino of a known (or unknown) mass, think of the situation as one involving three Feynman diagrams involving three different neutrinos $\nu_1$, $\nu_2$ and $\nu_3$. Each diagram contributes a complex number to the amplitude. By the rules of quantum mechanics, the three diagrams interfere.
Looked at this way, the mystery of neutrino oscillation becomes simply an interference that you're already familiar with. You'd have had the same type of interference if there were three possible energies of photons emitted.
For a reference to this way of looking at things, see slide 18 and following in Smirnov's presentation: http://physics.ipm.ac.ir/conferences/lhp06/notes/smirnov1.pdf