Newer generation of Cisco products have better speed/duplex autonegotiation with each other. Just to test, boot one and check with the other that the speed and duplex is full/100 instead of half/100 or half/10.
Otherwise, like what Jon said, force BOTH sides.