It's currently not possible to create a workflow for this case.

When a Contact is reassigned to a user, I want to be able to also reassign the Original Lead of that contact to the same (new) user.

When one tries to create the workflow as in the screenshot, Leads does not appear on the list if the action Updated Related Record is chosen. Kindly check the screenshot, because it's explained there how to reproduce this.

I have also opened a Case on the portal for this where they suggested to me to request it on this forum, kindly check case # 753.