When sending, if you open the Activity monitor in Mail, which apparently you have, you will a period in which it is in the process of connecting to the SMTP, followed by a period of Sending Data with % completed. Is the period of connecting quick and moves on to Sending data where it fails? If this is the scenario, then you may have an issue with MTU (maximum transmission unit) and packet size brought on either by something your ISP has changed, or by your Mac now sending bigger packets faster, until the connection times out trying to manage the transmission. See the following article about how to test if this is the problem -- also are you connected to a modem or router via ethernet, or to a wireless router via Airport?
http://docs.info.apple.com/article.html?artnum=303192
Let us know the result, and also how connected.
Ernie