[Evolution] Evolution & Paradise

[Bret Comstock Waldow <bwaldow alum mit edu>]

Hi,

I have been using Evolution for several years on various continents 
without problems.  Now I have an account with Paradise (via TelstraClear).

Evolution refuses to send mail.  It always claims the mailbox is 
unavailable:
"Error while performing operation:
RCPT TO <someone somewhere co nz> failed: Requested action not taken: 
mailbox unavailable"

I've tried this with several recipients, and the result is the same each 
time.

Mozilla will send the mail via Paradise, so I presume the account itself 
is working.  It appears to be Evolution specific.

Does anyone have any experience with this problem?

Thanks,
Bret