The solution was as simple as "ethtool -K eth0 tx off" on the domU's and "ethtool -K eth0 tx on" on the dom0's. After turning the tx checksumming off the network speed is faster and doesn't seem to be dropping packets at all anymore. I hope this saves people some time and I was not having fun at all trying to fix this problem.
http://lists.xensource.com/archives/html/xen-users/2007-01/msg00460.html