I'm not sure what would be causing this. Here's some approaches I've used to troubleshoot similar situations:

• I've had a few situations where re-deploying a report retained the previous parameters or parameter types on the report server, even though I'd changed the parameters in the redeploy(I'm a little foggy - this was a while back). I deleted and re-uploaded them to success. A better approach would be to copy both reports, modify the copy main report to point to the copy sub-report, and deploy both. Run the copy of the main report and see if the copied sub-report fails. If that works, then consider deleting and re-uploading the originals.
• Run a Profiler trace and see if the problem query execution returns different results than the previous executions of the query.
• Get the parameter values causing it to fail by adding a rectangle to the list/table holding the sub-report main report, putting the sub-report and some labels to capture the parameter values inside of that rectangle.

I'm surprised to learn that sub-query execution isn't logged to the ExecutionLog table in the ReportServer database. That makes troubleshooting this a little harder!