We encountered the same thing Bruno saw in comment #14. It was consistently reproducible on Natty when leaving tasksel blank (that is, only installing "standard"), but running a postinstall script that, among other things, pulls in fontconfig and ttf-msttcorefonts-installer in the same aptitude transaction (a metapackage which depends on both of those and a ton of other things. The problem is actually a poor interaction between those two packages. Two of my colleagues tracked it down:
1) Both packages are unpacked. Since it's part of ttf-mscorefonts-installer, /usr/share/fonts/truetype/msttcorefonts is created and exists.
2) fontconfig is configured first. fontconfig's postinst "helpfully" "cleans up" empty all subdirectories under /usr/share/fonts when it's upgrading from pre-2.4.0-1 (and since "" sorts earlier, it's triggered on a fresh install)
3) ttf-msttcorefonts-installer is now configured, and attempts to write the README to a nonexistent directory.
Arguably, fontconfig's conditional is wrong and should use "lt-nl", however msttcorefonts could also fix this by "mkdir -p" before writing the README file. Bugs will be filed for these issues, but I wanted to leave this comment here in case anyone encounters this in a Google search and wants to know what the hell is going on.