Hi, Sam:
Just updating this with some of our findings thus far.
The user can open the template and the already saved XML by using the URL to those items instead of opening from SharePoint.
Updating to SP 2 doesn't seem to have fixed the issue -- in fact, this same user has a laptop with Office 2007 SP1 on it, and he can open the template and any saved XML on that machine.
This has occurred to at least one other user.
This is their only form library, and you plan on creating another form library for them to see if it is something to do with the form itself.
The form template does not appear to have a publishUrl attribute, which strikes me as odd, and I've suggested you try republishing the template.