Problems with Mac on Windows network

Have you tried connecting using the PC's IP (go->connect to server->give IP)?
You should also try the Applecare search through Sherlock, it searches the same database as Applecare personel does
Keep us informed of your progress.

Hi Zippy, I was reading an article which had a link to a Microsoft KB article that may be relevant to the error you mentioned in your original post:

I get the following error:
The alias "computer name here" could not be opened because the original item cannot be found.