Hey Joe,
I know you said you don't have a firewall but here is my story and it may help. I actually have a very similar environment as yours (linksy DSL Router/Modem . Because of a recent incidence of a mass virus invasion on all 5 of my machines (4 XP pros, and 1 Win2K Server), i decided that i would put McAfee and Zonealarm on all machines.
Well all of a sudden (now that i think about it, it was after my Zone Alarm Pro trial ended), one of my machines couldn't see any of the others via the workgroup networking and vice versa. To make a long story short, Zone alarm on the machine in question, didn't have the other machines in a local zone. So the problem was firewall administration..