With lower performance, most opportunity for interference, greater cost and the need to have two short ethernet cables at each end, why? Ethernet is vastly superior, if you can run it.
I'd only recommend HomePlug for a situation where it was physically impossible to run ethernet. For those cases, it's a decent option.
Ethernet > HomePlug = Wifi, imho.
Whilst I completely understand the argument, and have had issues in my home with Homeplugs, Homeplug is definitely superior to WiFi when repeaters are used. I can easily cut a (measured) 50 mbps internet service down to 2 mbps when I use an Airport Extreme as the base station and an Airport Express as an extender. With a Homeplug I still get 20 mbps when I plug the Express into it. When I was using an iPad to watch video (BBC iPlayer) and using Airplay to push it to the aTV, the stuttering was awful. Now there's none.
My house isn't big or complicated, but the first set of Homeplugs I bought only worked between one side of an internal wall and the other - about 3 feet! I've since bought new ones - Netgear - and they're providing an excellent service to my aTV, Xbox and Tivo, with speeds well above the Airport Express. My AE now only provides WiFi to the mobile devices in the house.
To the OP - this is a really stupid, and potentially insulting, question, and I apologise, but are you sure that you've got iTunes running on the PC? I believe that, unless it's jailbroken, you'll only be able to stream stuff that you've got in iTunes, which for some reason has to be running, so that's what it's looking for...
You can check whereabouts the issue might be by using an iDevice, or other mobile thing. On an iPhone, for instance, running something like Splashtop would test whether the computer can be seen on the network by a device sitting next to the aTV. Also, AirVideo streams to iDevices and can be Airplayed to the TV (it needs a server downloaded to the PC as well as an app). Even better, you might also go into iTunes on your PC, play something (audio or video) and then choose aTV as your Airplay speakers (bottom right corner of iTunes). These will test that the network is working, but doesn't rely on home sharing.
Finally, just make sure that you've got both iTunes and aTV iOS up to date. From my experience, aTV connectivity has improved with the latest couple of versions of iOS. There have been several threads on here about aTV losing Home Sharing, so update everything, maybe including a restore of the aTV, and start again...
Hope you resolve it!
Tiptopp