I performed a soft reset and the same error messages were generated when I tried to send. I have not been able to send from this account.
Since this is a new phone, I would recommend a hard reset, then try configuring Xpressmail immediately. If that doesn't work call customer service. My reasoning is that you want to determine if there's something wrong with the phone. If you bought directly from AT&T, you have 30days to return. (Otherwise you have a one year warranty and you have to go through the warranty process.)