Duplexing is always one of them gotcha's when you see issues like this. Sometimes you can find that different vendors implement the duplexing detection slightly different which can cause auto duplexing to be done incorrectly. I always try to hard code my servers and network devices to a specific setting and ensure that the switch port that its plugged into is also specified. PC's are not normally a worry and i usually leave this just to auto detect.
I came across a really stupid duplex problem around 6 years ago. we had a 3com switch and a 3com NIC, they both didn't seem to implement the duplexing the same (go figure) and it always generated interface errors so we ended up having to set these types of NIC's manually.
Its very simple to see if you have potentially having these issues by viewing the port statistics on your switch, if you are seeing collisions and/or errors, then you may have a duplex issue.
Another thing to note here is that you will often see this get worse as you get more traffic going through the switch port. The more traffic that is generated, the more collisions/errors will occur. This will cause more re-transmits and will therefore generate more traffic, as you can imagine this can quickly spiral and cause some significant issues.