For all of those who are having this trouble and are beating your head against your computer screen because it isn't making any sense, let me share a solution I found to my issue on a Windows 2003 / Plesk 9.5.1 machine.
Plesk doesn't seem to always do all the things it should when creating...