You might have the same problem I had recently with the wildcard subdomain *.mydomain.com and webmail.mydomain.com.

Basically the problem is:
when you enable wildcard subdomain feature in Plesk 11 or 11.5 all webmails stop functioning, no matter whether it is Atmail, RoundCube or Horde.

I have contacted MediaTemple support but got no answer on this.

Here is a workaround i have found and it seems to be working fine.

Here are screen-shots how to deal with this issue.
Click for a larger view:

1. Add wildcard sub-domain

2. Go to the dub-domain hosting settings

3. Click on Hosting Type

4. Change type to Forwarding with you desired domain name

This is it, you suppose to be good to go.
I hope it will help you as well.
Cheers, Vadim