Basically you need to look in the result XML from your UpdateListItems call to find the value of the ows_ID node and use that for the listItemID value in the AddAttachment call:
My main function that is calling the sharepointServices:
//Add new Row to SharepointList
result = listService.UpdateListItems(strListID, batchElement);
//Add ...