Hola makeitslow,
he estado haciendo unas pruebas y creo que ya sé dónde está el problema.
En alguno de los mensajes te dije que utilizaras los archivos scriptaculous.js y prototype.js. Pues bien, estos dos archivos son los que tienes que incluir como estás haciendo, pero, además, hay otros archivos que tienen que estar en el mismo directorio que estos dos.
Descarga el zip de scriptaculous
http://script.aculo.us/dist/scriptaculous-js-1.7.0.zip
Y pon todos los archivos donde tenías prototype.js y scriptaculo.us.
Espero que funcione.
Saludos.
Se me olvidaba! Es muy importante que el siguiente código aparezca después de haber creado los inputs (cajas de texto).
Cita: <script type="text/javascript">
new Ajax.Autocompleter("nombre", "nombre_choices", "nombre.php", {});
new Ajax.Autocompleter("apellidos", "apellidos_choices", "apellidos.php", {});
new Ajax.Autocompleter("direccion", "direccion_choices", "direccion.php", {});
</script>