After a recent SharePoint migration from WSS2.0 to MOSS (database migration) I had one site that was giving the following error (screenshot below) when clicking "Fill out this form" in an Infopath form library:

(click thumbnail for full image)
The document could not be created. The required application may not be installed installed properly, or the template for this document library cannot be opened.

Follow up:

This was happening on 2 forms libraries on the same site, but I had forms libraries on other sites that were working just fine. On the problem site we noticed the nav bar on the list still has the WSS look and feel, and not the MOSS look and feel.

I got Microsoft PSS involved for about 3 hours and they couldn't find a solution. I ended up figuring it out on my own and here is the solution:

Long story short is the issue lies in the AllItems.aspx view for the forms library (or whatever the default view is). This can quickly be resolved by going into the list settings and creating a new default view. Here are the steps I followed:

1) Go into the list settings: can't do it the usual way given the state of the form. You can get in by going to Site Actions > Site Settings > Site Lists and Libraries. Then click on the problem list.

2) Create a new view, customizing it to your needs or to match the old WSS view. Click the box to make this your default view.

3) Delete the old default view. Odds are it was the one using AllItems.asxp. If that was the case go into your new view and rename the web address of the view AllItems.asxp

Your new view will have the MOSS look and feel and will now be able to fill out the Infopath form when clicking the "NEW" button.