Win7 PC Takes a long time to appear on local network

I have a local network set up in my home that consists of the following

cable modem -> separate wireless router

1 Main desktop, custom built, windows 7 - wired
1 e-Machines Windows 7 desktop - wired
1 Macbook Pro - wireless
1 Western Digital TV Live (media player) - wireless
1 iPhone - wireless
1 iPod -wireless

Problem: The main desktop PC takes a long time to show up on the network (5+ minutes). The other desktop, the Macbook, and the WD TV Live appear in seconds.

I use the main desktop with 1.5 TB storage to store media and I use the WD TV Live (connected to my TV) to play the stored TV shows and movies on my television. It would be a pretty slick setup if I didn't keep having network issues.

I don't know where to start troubleshooting this phenomenon, I've been Googling for hours and haven't come up with anything useful.