I think anonymous user doesn't have a permission of autocomplete. Can you please visit permission tab of your site. May be you get some luck!
Hold on, you are using taxonomy right, then please check this module permission. I think that time you get some luck.