According to Q238119 (http://support.microsoft.com/default.aspx?scid=kb;EN-US;q238119), 0x80040111 means MAPI_E_LOGON_FAILED.  This implies that SQL Mail tried to connect to the exchange server using the information provided in the mail profile and it failed.  Check your mail profile configuration.  See 
INF: How to Configure SQL Mail (Q263556)
http://support.microsoft.com/default.aspx?scid=kb;EN-US;q263556
for details.