Okay I think I figured it out.
Yeah I tested with my master account earlier, but it's still a valid point because Overwrite = * !* is removing overwrite rights from everyone, even master accounts.
So I decided to try with a regular account, and what do you know, I got the same error as you. But I quickly found out what was wrong - I uploaded foo.nfo with my master account and then tried to overwrite it with the regular account. DOH! Of course you get Permission denied when you try to overwrite someone else's file. When foo.nfo was uploaded by the regular user, overwriting it worked.
Case closed?
/ZR