Yes, you still have to skip the chosen phase or step this turn.
Fatespinner has a triggered ability ("At the beginning of each opponent's upkeep [..]") that creates a continuous replacement effect with a certain duration ("The player skips [..] this turn"). Once that trigger has happened and the ability is on the stack, the ability exists independently of the Fatespinner, as will the continuous effect that is created.
603.1. Triggered abilities have a trigger condition and an effect. They are written as “[When/Whenever/At] [trigger condition or event], [effect]. [Instructions (if any).]”
611.1. A continuous effect modifies characteristics of objects, modifies control of objects, or affects players or the rules of the game, for a fixed or indefinite period.
611.2. A continuous effect may be generated by the resolution of a spell or ability.
614.10. An effect that causes a player to skip an event, step, phase, or turn is a replacement effect.
112.7a Once activated or triggered, an ability exists on the stack independently of its source. Destruction or removal of the source after that time won’t affect the ability. [..]
It is, in principle, possible to word Fatespinner so that its removal also ends its effect. It would have to be worded according to this rule:
611.2b Some continuous effects generated by the resolution of a spell or ability have durations worded “for as long as . . . .” If the “for as long as” duration never starts, or it ends before the moment the effect would first be applied, the effect does nothing. [..]
For example, it could be worded thus.
At the beginning of each opponent's upkeep, that player chooses draw step, main phase, or combat phase. The player skips each instance of the chosen step or phase this turn as long as Fatespinner is on the battlefield.