The issue ended up being a firewall problem. I found it accidentally, but maybe the steps I took will help someone else solve a similar problem:

I decided to try using ODBC for the linked server instead of OLEDB. It's a roundabout way of doing things that you wouldn't normally do, but I was just trying to get some reports working again any ways I could. When I ran above query through the ODBC linked server, the results where very similar. I returned some of the rows and then threw an error. The big difference was that the error message was different. OLEDB gave a basically useless error message, but for some reason the error message through ODBC was actually useful. In our instance, the error message was 'bad packet'. I gave the error to our network admin, and he was able to find a solution within minutes.

So, if you run into this error, consider running the linked server through ODBC and see if it gives a different error message.