All of the networking mentioned above are excellent ideas.
As a network engineer who started as a cable puller many years ago, I'm going to emphasize the cabling knowledge as well.
About 90% or more of the network problems Network Admins run into are cable related. I work with many Net Admins who don't know anything about cabling, and they spend most of their time troubleshooting all of the complex things instead of checking the basics first. I've seen technicians spend days on a problem, because they don't believe me when I tell them that connections go bad over time and to recrimp the connectors and repunch the jacks. They will finally do that and the problem goes away.
Also, proper color coding is important. If someone is installing cable and thinks the color code doesn't matter as long as the colors match...they are asking for trouble down the road. The little things will pop up and kick you in the butt later on. Standards are there for a reason.
I've been working on these things for over 20 years now and I can't stand it when new a sys admin tells me that cabling is below him (bah!). I feel that a person can't manage the network if they don't understand the basics of the infrastructure. I recently inherited a network on a DoD contract. The cable plant is terrible, and the techs had no training. Panduit and Corning were kind enough to come in a train them for free (we buy alot of their stuff). Wonderful companies. It's amazing how much better things are running now.
Without a good cable plant, the routers, switches, and servers, are just expensive paper weights; and the Network Administrator has to be able to know where to troubleshoot. I require all of my Network Admins to help install cable until they are proficient at it. They start out hating it, but in the end they appreciate it. They start to feel much more confident in managing the network.
Now...with my babbling out of the way...
TCP/IP knowledge is very important. OSI very important. Good OSI knowledge can cut down troubleshooting time immensely.
IP subnetting.
Basically, a good foundation of knowledge for internetworking. Teaching industry standard instead of vendor specific. The vendor specifc training would then come as additional courses.
Cisco training materials are excellent. Even though they are from a vendor, they teach networking fundamentals from a standard approach instead of a vendor specific approach.
Microsoft is finally making changes to their materials. Their old TCP/IP books were crap. They taught TCP/IP the microsoft way and just confused everyone.
I could go on for days about this, so I better quit. heh.