Figured it out... The reason was because I had the DNS Blocklists and URI DNS Blocklists setting activated in the AntiSpam Tools page. (Gee, wonder why I did that?)
Come to find out from this forum that the reason users couldn't join was because I had zomqbl.spameatingmonkey.net. enabled. (Silly me.)
I disabled the spameatingmonkey and it works fine now. Kinda sad because I like the name spameatingmonkey. It has a nice ring to it... Oh well...
Why that would cause people not to be able to create accounts at my site makes absolutely no sense to me whatsoever but whatever, it's fixed.