I've just suffered through a problem like that; it turned out that Plesk wants you to change your DNS settings at your domain's nameserver (i.e., this is OUTSIDE of Plesk), so that "webmail.yourdomain.tld" is listed on the nameserver with the server's IP address, along with the more usual "www.yourdomain.tld", etc.
It would be very useful if Plesk could ping webmail.yourdomain.tld when you are setting up eMail on Plesk and let you know there's stuff you have to do outside Plesk, but this doesn't happen.
Having fixed that problem on my machine, I have now run into a new problem: when I attempt to log into webmail.himivest.com (which is my website), I get one line of text on my browser "No input file specified."
I think this is something to do with php settings, but I don't know.