Which make/model of NIC are you using in the Linux machines?
Do lsmod and find the names of the networking modules loaded.
How are your eth~ interfaces configured? static, dhcp.
What does ifconfig show, MTU etc?
I am aware of some timing conflicts between different brands of NICs and hubs/switches which can slow traffic, but this is usually in both directions...
Because you don't get an automatic 100MBps connection, I would suspect the NIC drivers aren't working properly.
Have a look in /var/log/boot.log for NIC connection messages.