This could have a myriad of causes.

Could you perhaps elaborate on the connection / authentication types used in your reports ? are there specific error messages generated ?

The most obvious error I've made that gives this problem was using windows-authentication to the datasource, and not setting up the pass-through properly on the web-service.