RESOLVED:
After hours of looking into this more, I found that using the Cimy User Fields plugin was giving a conflict. First, I deactivated all plugins, tried to add a new user and it worked! I then worked through all of the plugins by activating/deactivating each to find which one was giving the conflict. I then upgraded the Cimy User Fields plugin to the latest version and, voila, no more issues.
-tB
