It sounds like you aren't actually applying and saving the effect after you preview it.
Any chance you are using Nero Wave Editor? If so, when you select "Tools"->"Time Correction..." you get a dialog box from which you can play with the time expansion/contraction settings and preview the effect. When you are satisfied, you press "OK", the settings are applied, and you can save your work. Right? Wrong!
The settings are only applied to the portion of the waveform that you selected before opening the Time Correction dialog. You probably just had the cursor placed on a single point in the waveform so that no range was selected and the effect wasn't applied to anything. Thus, you saved the waveform exactly as it was - unmodified.
The trick is to make sure you have selected the portion of the wave you wish to modify before selecting "Tools"->"Time Correction...". It seems that you wish to apply the effect to the entire song, so the easiest way to do so is to select "Edit"->"Select All" or simply press Ctrl-A. The entire waveform display will switch from green on black to blue on white, and when you subsequently select "Tools"->"Time Correction..." and apply your effect, you will actually see the waveform stretch. You will also now be able to hear the effect when playing the waveform using the CD-like controls on the lower left on the screen. Now save, and you should have the modified file you want.
Even if you aren't using Nero Wave Editor, the same general comments likely apply. Make sure to select the portions of the waveform you wish to modify (in your case the entire waveform) before bringing up the time correction dialog box.