If you have a system that might be changing versions multiple times you might orphan some of the lateral utilities (like newaliases). If you want to be certain that you're rehashing the correct aliases file (the one that sendmail.cf is referencing), run sendmail with the -bi option like this:

# /path/to/sendmail -bi