I have seen an issue with SharePoint 2007 where an a %25%20 got inserted into the template URL in all forms in a library instead of %20 (there was a space in the URL of the library and it should have been %20 only). This appeared to happen when files were moved into the libary and re-linking in SharePoint did not work properly.
The interesting thing was that we had the same issue with some users being able to open the same form fine and others could ony open the same form in Read only. Turns out that the users who could open the form were using InfoPath 2003 and the users who could not open the form were using InfoPath 2007.
The issue was fixed by relinking all forms.
Not sure if that will help in your situation but thought I would mention it.
Ted