I eventually wound up checking the McAfee firewall settings on the various machines. None of them were allowing ICMP ping requests, so when I fixed that I was finally able to ping machines from one another, but Windows was still fubar. Then I went and looked at the allowed/disallowed hosts entries in the firewalls, and they were all weird (including multiple conflicting entries for my local subnet), so I cleared all of them out, made the local subnet trusted, etc. That made the McAfee view of the network map correct (i.e., each machine could see all of the other hosts), but Window sharing was still not working.
Finally, fed up with all of that shit, I just disabled the McAfee firewalls, and bingo! everything was fine. For now, I'm leaving things like that until I get some more time, my rationale being that the firewall in the router should protect me from bad guys outside my subnet, and everything inside the subnet is trusted anyway, so if some malware gets in there it's going to eat my lunch anyway.
The big mystery here is how things were working before I swapped routers. It seems unlikely that the Cisco/Linksys installation software was smart enough to figure out that I had the Windows firewall disabled and the McAfee firewall enabled, and then use some McAfee API to change McAfee firewall settings. (Maybe those firewalls plugin into some generic service, so that clients don't need to know exactly what implementation is running.) Based on the various changes that I had to make, it seems like I should have been equally screwed up before the swap. But I wasn't, so there's obviously more to this story than I understand at this point.