So I did some more digging. I ran tcpdump with a variety of filters (essentially using grep), trying to find out what might be happening.
I found that the problem is unique to my server, as clients can nfs betweeen each other with good transfer rates, bidirectionally, at good rates (10 MB/sec) using large files for testing (time dd). Any of my clients has a problem with the server, and none of them have a problem with each other.
Most recently, I found when the errors are occuring, there is a Unknown rpc response code, which appears to be regularly changing.