• Open Control Panel
• Click Programs
• Under Programs and Features there should be an option that says “Turn Windows features on or off”, click this.
• On the list that appears simply choose: Telnet Client

Simple as that, and the telnet client is included again. I don’t know why they don’t install it by default, it’s < 1 MB and incredibly useful.