Mine does not work whether I have full trust enabled or not.
The answer from Microsoft is that this is "Expected Behavior". Ironically, they didn't give me that answer right away. I worked quite a while with two support specialists to try to resolve the problem. Then, when they found out that it couldn't be solved, they claimed it was not a bug, but in there by design. How they said that with a straight face, I'll never know.
The issue is that in order to add a document, you need to perform a "check-out" or "check-in" procedure which requires not only the Add right, but the Edit right. And of course, the Edit right allows users to change existing documents, which is unacceptable for some applications.
I found this link about the subject after I posted; it has some workarounds for the problem:
http://www.infopathdev.com/forums/topic.asp?TOPIC_ID=2161