I know this is a year ago, but I recently encountered this problem. And I thought I'd share my experience and save someone from frustration.
Although the solution above was good in telling me what was causing the problem, I still had to try and figure out where the problem is.
In my case, I copied an existing and working page that has a
DataFormWebPart which shows a view of a form library. In that copy, I edited the filter on the
DataFormWebPart to show a different set of forms. My testing worked until my user tried it and got the threshold error message. The threshold is higher for site collection admins, so I didn't get the error when I was testing the new page I created.
So I went to look for the cause of the threshold error message.
In Sharepoint Designer, I normally use Data View Tools > Add/Remove Columns, (on the ribbon) to check the columns included in my
DataFormWebPart. Everything looked okay. There was not a single lookup column in the view.
Then I decided to check the Data Source Details. (If you do not have the Data Source Details window open, you can do so via a toggle button on the Options tab of the Data View Tools ribbon menu. Then on your Data Source Details window, click the name of your data source to bring up the properties popup window.)
On the Data Source Properties, I clicked the Fields... button and then I noticed on the Displayed fields section, it shows a number of form fields which are not shown in the Add/Remove Columns. So I tried removing all fields except those I needed to properly render my view. And that fixed it!
You probably would not need to remove all fields you do not use, but you certainly need to reduce the number of lookup-type fields