Okay, sorry for not responding earlier but we just weren't being patient enough and were working on moving to production and didn't have a lot of time to work on it. It does eventually return values it just takes a really really long time. We've been seeing other performance issues on the site so maybe if we find a solution to this we can solve the others. None of the other performance issues are anywhere near as severe so it may be entirely unrelated.
I'm accessing it mostly in Google Chrome but it's the same in FF, haven't tried it in IE. In the network tab of Chrome's Developer toolbar it ends up taking somewhere between 1.6 minutes to 2.7 minutes to get about 133k of data from:
It returns 60 items. Then it looks like it turns around and hits that web service again which takes something like 5 minutes to respond. Although after the first response the page templates load... On the timing tab it looks like most of the time length of the call is spent waiting: 1.6 minutes.