NOTs in SUMPRODUCT and other array formulas can be quite tricky.
Paul is right, the <> version that you are using is comparing each of the constant values against each of the cell values, so many are being counted multiple tim4es.
The = test you originally used was using a neat shorthand version, but the not equal version can still be handled by SUMPRODUCT, by using a more 'structured' approach, using MATCH.
So here, we would test whether any of the constant values are in the range using
MATCH(MyContacts!$B$1:$B$4000,{"Teacher","","NA",1967,1976},0)
This returns the position of the cell value in the constants array, or #N/A if not found. So we turn this to TRUE or FALSE by using ISNA against it
ISNA(MATCH(MyContacts!$B$1:$B$40,{"Teacher","","NA",1967,1976},0))
Unfortunately, the blank test does not work as you have it, so you need to add another test for that
--(MyContacts!$B$1:$B$40<>"")
In full, to get your count
=SUMPRODUCT(--(MyContacts!$B$1:$B$40<>""),--(ISNA(MATCH(MyContacts!$B$1:$B$40,{"Teacher","NA",1967,1976},0))))