Just out of curiosity: did you upgrade your nagios from v2.x to v3 ?
if it is the case, I'd suggest you have a look at your command definition for your "notify-by-email" command: some variables have had a name change and it may be the cause of your problem.
and if not (ie: you've got a clean new installation of nagios)...I don't know what could be the cause; but just in case, you could check what I said above :).
Either way, it may be the same problem as in this post meulie.net/portal_plugins/fo ... .php?11331
And to finish: if you can't find the solution, please post some of your configuration settings (like contacts definition, contactgroups definition, service definition, commands definition...etc)