This is exactly the answer I was looking for.
I don't know who you are Andrea but I've seen your answers on lots of other posts and you seem like the answer to any wordpress problem. Thank you.
For the benefit of anyone else who might run into a similar problem, I'm going to explain, in detail, what my problem was and how I fixed it, exactly.
I use Wordpress MU and have a baby gator account with hostgator. I have a maindomain.com and several add-on/subdomains. I create a new blog with the URL newblog.maindomain.com, and I use the Domain Mapping Plugin to change the address to newblog.com, since my maindomain website has nothing to do with my newblog website.
So, I created, let's say, newblog4.maindomain.com, and I assigned newblog4.com to it using the Domain Mapping Plugin. I thought I had made a mistake with something, so I deleted newblog4 from WPMU and I deleted the add-on domain (which removes the subdomain as well). Later on, I created newblog5, and tried to assign the old newblog4.com to newblog5.maindomain.com using the Domain Mapping Plugin. It wouldn't add it! Then, I realized, that I forgot to remove the domain mapping from newblog4 before I deleted it.
So, somewhere, something remembers that newblog4.com is already assigned. I guess you can't assign it twice. What it was assigned to is gone, and I need to assign it to my new blog, newblog5.
I contacted hostgator live chat support twice, and both times they assured me the problem was not on their servers and that I had to contact the software developers. I also could not find anything on the internet. Thanks to Andrea, I found the solution.
When you use the domain mapping plugin, it "remembers" what you assign in your database. Go to myPHPadmin, go to the database you are using, and look for "wp_domain_mapping" - When you click on it, click "Browse," and you should see a list come up. This is what it remembers. Here, I saw my newblog4.com. Select what you want to remove, and delete it.
This is what I did, and now newblog4.com is working properly with my WPMU install.
Of course, always make a backup before you mess with anything.
I hope that any of this comes in handy to at least one person - I'm not the only rookie out there.