Found it ...
When I setup the server initially, I had configured my own DEFAULT FPT entry in IIS. I deleted this and the domain creation process went through without the error.
Note to the Plesk installers: Make sure no DEFAULT entry exists in IIS when you setup Plesk for Windows ...