Are you get this error while using the updatelistitems method in SHAREPOINT web service (list.asmx)?
Are you aiming to data stored in a subsite?
If so, the solution is to point the webservice of the subsite directly.
If your main site is http://cia, and your subsite is http://cia/coa, you should point to the webservice:
http://cia/coa/_vti_bin/list.asmx
Pay attention that, sometimes, when you update the webreference, in the app.config it remains the same. So change it there as well.
Good luck!
Once you have the AR established, then you can COPY your entire contact list from its existing list, into the new AR List. Yareli Webservice