Ugh. Even though I often support it, sometimes I really hate Windows.
So today I went back and tried all the suggestions here that I hadn't tried yesterday, as well as some other stuff I looked up. NOTHING was working, and every single help thread I read on the subject was pretty much worthless or didn't have the problem solved.
But then, buried deep in a very long thread was a post that I happened to stumble on because I was at my breaking point and just reading everything I could. That post suggested something: make sure the computer name doesn't have a hyphen.
Now, sadly I can't be 100% certain if that's what fixed my problem or not, but all I know is that sometime before I changed the name of a particular problem PC I was working on, I was still having problems. Sometime after I removed the hyphen, it was working. If that is the case, it really pisses me off, because nowhere does it say that you can't use a hyphen in a computer name.
Now, I still was completely unable to get all the computers seeing all the other computers in the Network area. Unrelated to Windows version, some would show all the computers, some would only show like operating systems, others would only show a couple computers, other's wouldn't really show anything, and they all seemed to be set up right.
Clearly, MS has not done this correctly over the years, though I guess they're trying to get it right with Homegroup (which I still have several problems with).
Oh, and lastly I must reiterate how much I despise McAfee and Norton. Norton didn't give me any problems today, but McAfee completely blocked Windows file sharing for any computer it was installed on. Even when I added an exception for it in their POS interface, it still didn't work. So I uninstalled it from all computers and put MSE on...
_________________________
Matt