Yes, that's true. Some newer NICs provide an internal crossover detection and correction. Look for the notation Auto-MDI/MDI-X or some other auto uplink notation on the NIC box.
But we are assuming that the NIC has this. If it does, great, the crossover cable isn't going to hurt. If it doesn't, great, the crossover cable will provide connectivity.
So to recap, there could be two things to look at here. Firewall software and Cabling. Certainly, if a firewall is installed on one of the machines and not the other, this could be blocking the ICMP traffic. Norton is notorious for this. This would prevent an echo reply from the firewalled machine. If that is the case, disable the firewall and try to establish connectivity again. If this doesn't work, then we digress to the OSI layer 1 issue here....the cabling.