Problem Connecting to Network?

A PC running vista should not be a problem for you, even if it was it would not interfere with the tv joining the network. Is it possible that your tv is either too far away from your base station or that it is in another location from your PC and base station and suffering interference that the PC and base station are not.

What sort of encyrption are you using to secure your network.

If you're using a router and Apple TV can't establish a connection with it then it's unlikely that the problem is related to your Dell PC. It's more likely to be a problem with DHCP or security settings either in the router or the Apple TV. If your Apple TV is properly connected to your router you should see a network IP address of something like 192.168.x.x.

iMac Mac OS X (10.4.9)

I had a similar issue and it was router-related - I had to upgrade the firmware on my router and it solved the issue (although I'm still losing the connection whenever I switch the ATV off).
More info here:
http://discussions.apple.com/message.jspa?messageID=4310246
Have you tried plugging it through an ethernet connection to see if that works?

I had the exact same issue. Where did you put your Apple TV? I had put my Apple TV on top of my VCR. It would see my wireless network, but would never connect. I put it aside and it was able to connect. You might want to try this.

This is really weird, and it does force you to find another place for your Apple TV, as you cannot stack it now.

-Nags

I don't suppose there's an 800 number for support on
this thing, is there?

Of course there is. Check your warranty info. In the US, you get 90 days of free phone support without buying an AppleCare Protection Plan, 2 years with one.

You can't assume that it's not your router just because other devices can connect. I've seen a lot of buggy firmware in routers sold for home use that result in two different devices being assigned the same network address via DHCP, for example, or not responding to a DHCP request from a particular device.

iMac Mac OS X (10.4.9)

That's true, when I was having my router problems I had two laptops (one macbook and one PC laptop) both connecting fine to the wireless network.

In your router settings, make sure DHCP is enabled. You should also set a WEP key in your wireless security settings if you haven't already. If you enter a new WEP key you will have to change it in all of your wireless devices, not just your Apple TV. Also check to see if your router is restricting access by MAC address. If it is you will have to enter your Apple TV's MAC address and allow it access.

In your Apple TV go to the network settings and let Apple TV search for a wireless network. You should see your router's network name, probably something like "Westell_ABC" or perhaps something more cryptic like "80097_C." Select that as your network (make sure you don't select your neighbor's wireless router if there are other wireless networks near you). Enter the correct WEP key and make sure DHCP is enabled and it should work.

iMac Mac OS X (10.4.9)

Also you should try it at least once with the ethernet connection (and I know it's a pain...). First you will be able to confirm that the problem is in the wireless connection and not in the ATV itself, and second you'll be able to do one big sync of your iTunes library, assuming it connects... Which should at least get you started.
If the Ethernet doesn't connect I would bring back the box.