After an hour of freakin' out over the "Network not found" message, I finally joined this forum (about time, I've had my Touch for around 15 years) and realized that I hadn't done a full factory reset.

Success - the new year is truly off to a good start!