Have you tried connecting to the PC via IP address, instead of computer name?
Is the firewall on the PC perhaps blocking the traffic?
Are all sharing services (SMB, etc.) turned on on either computer? Just to clear that up: you do NOT need to turn on "Windows sharing" to connect TO the PC FROM the Mac, but you do need to turn on "Windows sharing" to connect TO the Mac FROM the PC.