<script type="text/javascript">
new Ajax.Autocompleter("autocomplete", "autocomplete_choices", "ajax.php?mode=tagsearch", {});
</script>
No se si es tarde y lo solucionaste, pero el metodo Autocompleter toma como referencia en este caso "autocomplete" la variable a enviar y luego estas enviando mediante "ajax.php...."otra variable mas. Bueno visto esto tienes que procesar la respuesta en el formato
<ul>
<li></li>
<li></li>
<li></li>
</ul>
Asi lo reconoce el autocompleter y te muestra en autocomplete_choices.
Espero que tenga razon ñ_ñ
Saludos