You can not just preserve original phase when doing time stretching, there are "smarter" algorithms that try to derive "correct" phase, while the paulxstretch just make it random values, maybe for extreme stretching values it doesn't matter for ambient music but for general music and sounds its not that trivial.
There is some signature compression that comes with paulstretch that sounds exactly like the output of a square wave interpolated to a sine.
You can see, hear and almost taste it if you stretch white noise.
Tonality makes no difference.