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
If I understand correctly, neutrinos all have a "mass-basis" which is essentially the state of the neutrino that includes its mass and probabilities for what flavor the neutrino interacts as. Neutrinos are created with a particular initial flavor which has a probability of having one of 3 non-oscillating mass-bases ("bay-sees"?), conventionally called
Saying for example that an electron-neutrino has a particular mass, is misleading. Instead it seems that a neutrino created as an electron-neutrino has a probability of having each mass-basis, and that mass-basis determines how the neutrino will oscillate its flavors.
Read this for a good non-mathematical explanation: http://www.quantumdiaries.org/2010/08/02/solar-neutrinos-astronaut-ice-cream-and-flavor-physics/ . Thanks to Marek for putting that link up there as a comment!