Check Settings » General and make sure WordPress Address (URL) and Site Address (URL) are both set properly. Then go to Settings » Permalinks and reset your permalink structure.
Also, you should do a global find in your database, but not necessarily replace (although if you're doing a find/replace from atlas.site.com to www.site.com or site.com it should be safe). Either way, back up your database before doing any global operations.
Edit: Okay, one more idea then I'm stumped. Try the Relocate Method - add this line to wp-config.php before the "stop editing" line: define('RELOCATE',true);, go to wp-login, log in as normal, go to Settings->General, make sure both URL's are correct, save settings, then remove that line from wp-config.php.