Mail, email, user registration, change password not working

The emails that presumably get sent upon user registration and when requesting a new password are not working. I've checked the php settings, I've written a simple email script and called it directly (works fine), but my Drupal installation cannot send mail. I installed the smtp.module which I read about here http://drupal.org/node/view/7232#10957, and nothing changed. I don't know how to go about testing and debugging from here. Any suggestions?

Thanks,

-Robert Douglass