I can't see how they can say that they have seen this before as essentially the avast Mail Shield in both free and paid versions is the same.
Which avast version did you purchase, Pro or AIS ?
How did you upgrade ?
What is your ISP and doe they require SSL for their email account settings ?