Many older Ethernet PHYs do not support auto-mdix. Therefore the first thing I would try is changing the cable. If your current cable is straight through try a crossover, if your current cable is crossover try a straight through cable.
If that doesn't help then I would try looking at what speed and duplex mode they negotiate with the PC. In particular is it the same for both devices? This may provide some hints later when trying to find a configuration that works. If the PC is running linux you may also be able to use ethtool to look at the "link partner advertised link modes", that is what link modes your embedded device is advertising (however this doesn't always seem to appear,
Most Ethernet devices can have their speed and duplex settings controlled by software. Googling your operating system and/or platform name followed by "set speed and duplex" may help turn up some instructions. If they are Linux systems then "ethtool" can usually (apparently not all Ethernet adapter drivers support it) be used to either disable autonegotiation and force a specific speed and duplex mode or to leave autonegotiation enabled but restrict the modes that can be negotiated.
Note that having autonegotiation enabled on one end and forced full duplex with autonegotiation disabled on the other can cause a duplex mismatch which will lead to horrible network performance. If you want to use full duplex you should either use autonegotiation on both ends or manual configuration on both ends.
If you really can't get the devices to talk directly to each other you may have to workaround the issue by inserting a switch between them. Obviously this comes at a cost which may or may not be acceptable for your application.