Try another cable, it wouldn't be the first time someone picked up a normal cable thinking it was a crossover.
I don't use windows firewall, but if your machines don't have a connection to the internet, switch it off - the firewall may disable discovery of the machine. If you are connected to the internet however, I wouldn't recommend it.
If you know someone with a hub, try testing with that.
Check that the machines can ping each other, click start...run and type cmd. In the command window, type
ping <other ip address>
and see if you get reply messages.
Also, type ipconfig /all on each machine and let us know the output.