I'm closing the loop on this distcc problem. It turned out that the problem was indeed because of the TCP segmentation offload bug in kernel 3.16, described in this post: viewtopic.php?f=9&t=7692&start=10#p42153
I've rebuilt Debian kernel 3.16 with the patch to set TCP segmentation offload default to OFF. And upgraded the kernel on all distcc client and servers to 3.16. Everything is woking normally for distcc compilation.
Thanks ebbix for the fix and kmihelich for the kernel patch posted in the above thread!
-bodhi