This is something that I've been meaning to delve into for a while now. I've used the AjaxControlToolkit AutoCompleteExtender a bit but until now I have never had to pass a runtime parameter through to the service method.

I found a post saying that the signature of the method must be the following: 

[WebMethod] public string[] GetCountryOrStatesInfo(string prefixText, int count, string contextKey)

For some reason I took the signature part to mean parameters string, int, and string in that order. As it turns out the parameters must be named exactly prefixText, count and contextKey. You will also need UseContextKey="true" on the AutoCompleteExtender in your aspx as well.

In the example I was doing, the context key was state and on the selected index changed of a combo I was setting the context like this:

AutoCompleteExtender1.ContextKey = ddlState.SelectedValue; 

One other point of note, the web service class itself must be decorated with [System.Web.Script.Services.ScriptService].