Our current migration from MOSS to SP2013 has been interesting, needless to say. Because I am an administrator I never see these little issues. This is one of the latest fires I had to put out. This popped up for different users whenever they would click on new document. At first, I thought it was s permission issue, but that was not it.
Turns out that this is an issue with Internet Explorer 8 (of course). The new document + calls a javascript function that ie8 cannot recognize. Instead of opening the web based InfoPath form, it tries to add a document. After testing on other systems using ie9 +, Firefox, and Chrome this is the only logical explanation.
To address this issue, I had to add a Page Viewer web part to a page and link to the opened view of the form. Not the most elegant approach, but it works.
Stay Salty!