Saw your Stack Exchange post but it looks like they closed it to additional answers.
admin-ajax.php is the standard way to do AJAX in WordPress, for both admins & regular users. At one time it was just used for the admin screens, but they decided to re-use it for everybody and now we're stuck with it.
Usually when I see this issue, it's because someone added a rule to their .htaccess file to password protect the wp-admin directory. I know there are a lot of tutorials saying to do this for security, but you need to open up access for admin-ajex.php and a few other files.
I really recommend this page in the WordPress Codex on hardening WordPress and this blog post with a better .htaccess configuration that allows access to the necessary files.
Hope that helps!