Buenas,
Efectivamente no funciona el autocomplete con nuevos datos cargados porque cuando utilizas la funcion
autocomplete se realiza únicamente sobre los datos ya existentes.
Tendrás que recargar el código en el click del botón añadir.
Fíjate en el siguiente código (es un concepto):
http://jsfiddle.net/alexg88/7ehtb/
Un saludo.