Not really knowing what you've already done....
If you are using rules in sharepoint lists:
Sounds wierd but re-do all of dataconnections then republish and upload.
If your sharepoint is a farm with multiple front ends it could be that the form didn't deploy properly to the additional.
In any case check the solution store in central admin and check that it has deployed correctly.
Create a new list and assign the the same content type. Check to see if you still get the error from the users who having difficulty.
Check the timer jobs and timer difeinitions in central admin. (looking duplicate jobs and failed deployment, deleting any jobs that may causing problems)
Check the features folder in WSS/MOSSPath\template\features, look out for multiple versions of the same form.
Stop and start IPFS via stsadm
If you still have issues you may consider stripping the form out completley and reinstalling it. sounds agressive but there are several things you can do with the list items which need to be gone before you delete the content type.
Once the content type is deleted:
Dactivate the form via forms management central admin
Then delete it.
Then away you go again.
Hope this helps