I met the exact same problem today. I tried carriemulcahy's trick but it didn't work for me. In the end I managed to find another fix:
My wordpress 3.5 is running on a AWS LAMP server. I have setup the multisite network and I can access the dashboard of site1.main.com and site2.main.com. But after I installed the MU Domain Mapping plugin and changed the site2.main.com to site2.com. (I used the "by configuring virtual hosts, specifying the same document root for each" option here.)
After that, I can only view the site, which means the DNS and etc works fine. But I can not access the admin dashboard of the site2.com.
I found two fix:
1) Disable the Domain Mapping on network. Go to dashboard of site2.main.com. Enable the Domain mapping plugin there and set the site2.com there. You will be able to have a site2.com wordpress site and a site2.main.com/wp-admin backend.
2) Enable the Domain Mapping on network. Besides all the official plugin setup instructions, you also need to add your site2.com in the "super admin->settings->domains".
Hope this will save someone sometime.