FYI - I have been experimenting lately on the treadmill due to the white and slippery stuff on the ground. The nike+ is more accurate if you run toward the front of the treadmill versus the middle or trying to keep up position(why not recalibrate? - because I usually like to run outside and did not want to have to keep recalibrating).
So, Try running up front for better treadmill to mileage matching.
That still does not explain the time travel issue I have noticed - treadmill starts up - runs for 15-20 seconds then I start the nike+ and then later when looking at the times they are the same or the nike+ is ahead of the treadmill...weird - so it is hurting my pace if there is a time issue - but is it a slow clock on the treadmill or a fast on on the iPod? Who knows?
i'm not sure about the time thing. i would like to think it wouldn't be hard for the nano to keep track of time....