hey -

I'm by no means one of the gurus on this site, but whenever I've run into this it's been permissions issues. Make sure the account that SQL Agent runs under has enought rights to send mail.

I vaughly remember something about proxy accounts set up for email purposes, but I can't remember enough about it other to give you another thing to look for.

sorry if that's not much help, but one of the gurus will probably jump in before long.