Send Email when sql server agent job fails
For 2005 and 2008 you need to configure Database Mail then enable the Agent to use it (SQL Server Agent --> Properties --> Alert System). If problem persists, you can query the system tables related to Database Mail (check BOL for names of tables) for possible more information. If problems still persists you may need to work with your Exchange admin.

For 2000 you need Outlook installed.