Well, not so much coincidence as just untrue.
His leaving Manchester United had no effect because Steve McClaren was immediately installed as his successor. For a view of what happens when United lose their top coach, reference last season. In the same way that Kidd is a far better coach than a manager, Fergie is a no kind of coach at all - he is all manager. Equally, it is no coincidence that United have begun to improve again since that Portugese wallah was appointed in the summer.
Everything I have read about his time at Leeds suggests he has been a very big success there.