2
What settings are you using in System -> Preferences -> Mail Setup?
Can you turn on PHP debugging and try registering an account to see if there are any errors returned by PHP?
If no errors here, try sending a test message to the Webmasters group in System -> Mail Users
If that works with no errors, the next spot to check would be the sendmail logs. Check if the user registration messages actually made it to the mail server.