Are your users using browser based InfoPath? If so, and you are using the rich client, that could explain it. You'll need to create a UDC connection for the Web Service. Go to data connections and click Convert and browse to the Data Connections Library on your SharePoint site where you can save the UDC file.
Is the Web Service on the same machine as the SQL database? If not, the above connection strings will need to be updated.
Do the users have access to the databases you are querying? If not, you'll have to add then.
Just trying to think of other reasons... running out of ideas though ....