Interesting, does it work when port 25 is blocked? looks like it use port 587.
Anyway, have you changed the mail commands? I am also using ubuntu 9.10 and I had to change '/bin/mail' to '/usr/bin/mail'.
instead of mail email@example.com try the full command line use in the nagios command file.