I logged in as root and visudo'd /etc/sudoers.
I found several users with the username ALL=(ALL) ALL entries and added an account after the last one.
Saved the file.
When the user logs in and does "sudo su -" they are prompted for their password and then told they are not in the sudoers file.
Is there another step to "activate" the change?

There's not another step, no, if you edited the file properly. It sort of sounds like you did, but there's also hints you didn't; you don't visudo /etc/sudoers, just visudo... Did you use visudo, or did you vi /etc/sudoers? visudo should run by itself, without any filename arguments.

I did only visudo.
There are several entries for users with root priv and I inserted a new line after the last user.

Check the line closely for differences. If possible, post it literally.

Here is the section from /etc/sudoers where I added newuser

##
root ALL=(ALL) ALL
user1 ALL=(ALL) ALL
user2 ALL=(ALL) ALL
user3 ALL=(ALL) ALL
user4 ALL=(ALL) ALL
newuser ALL=(ALL) ALL

##

Where do you see you have no password?

I logged in as root and did visudo
Then I logged out of root and logged in as newuser
Here is the screen:

[newuser@zwork ~]$ sudo su -
[sudo] password for newuser:
newuser is not in the sudoers file. This incident will be reported.
[newuser@zwork ~]$