I have nearly the exact same problem with three of my machines. two of my win98se machines couldn't access my XP machine. This also started up just a few days ago (the 11th) out of the blue with no real explanation. And I CAN connect to the internet with all the machines. (its so similar its spooky, virus? I did a scan just lastnight and it didn't find anything but hey who knows)
A work-around I found that if you change your workgroup on all machines to something else (in my case from "HOME" to "WORKGROUP") that everything settles down. Though I do have the problem of the old computers/workgroup not disapearing >
. I currently have dead links to my XP machine that I dont know how to get rid of. If somebody could help me figure out how to delete my old workgroup I'd be much abliged!
UPDATE:
Well the workaround seems to have just killed itself >:|. Just a minute ago I COULD access my XP machine but now I can't. The error Message I get is slightly differant than yours (probably just because it's windows 98SE instead of XP) I get "\\(name) Is not accessable, the device does not exist on the network"
....GRRRRR!!!! Now I can access it again! It changes! And the "HOME" workgroup is empty now that I finished moving all the computers over to the new network. but the workgroup "HOME" it's still listed under the workgroups (maybe a restart will fix it). Something definatly freaky is going on here.
Yup, restart fixed the "HOME" being listed but access to my XP is still intermitant