In 1972, in Anti-Oedipus, Deleuze and Guattari make no mention, as far as I can recall, of smooth and striated space, or even of the nomad. (If there is it is hardly front and center).
Then, in 1974, Pierre Clastres publishes Society Against the State, wherein:
The space of nomad hunters [the Guayaki (or Ache) people of Paraguay that Clastres was studying] cannot have the same dividing lines as that of sedentary agriculturalists. The latter is structured into concentric circles, with a division between a cultural space comprised of the village and gardens, and a natural space occupied by the surrounding forest. In contrast, the Guayaki space is continually homogeneous, reduced to a pure extension in which the difference between nature and culture is seemingly done away with….
Then in 1980 in A Thousand Plateaus, we get the whole discussion of the nomad, smooth space, and striated space. I am only halfway through Clastres, but so far it seems pretty clear that he made a very big impression on D&G.
Path to the Possible 
You may also find Clastres’ ‘Archaeology of Violence’ useful.
See the e-copies on https://docs.google.com/folderview?docId=0B4os7g99Xa8BOGFlYzMzZjItMWFmNi00ZTMwLWJlMjgtOWY1ODBkMGRjZTI0&id=0B4os7g99Xa8BN2YyODZkNjctYTRhNS00YWZjLWI3NTgtNjUxZDRjMTFlM2Zk
Thanks, I will have a look! (The whole page is a great resource!)
Guattari talks about Deleuze’s love for the nomads in the Anti-Oedipus Papers. G says that D started working on them immediately after AO was published.
Others have noted that Clastres broke with his mentor, Levi-Strauss, to collaborate with D&G on AO. Really too bad that he died so early into their collective work – the anthropology piece in AO is so strong and it is not nearly as strong in ATP.
How fascinating, what were your thoughts on finishing the book, have just come to your blog recently. Thanks for insight – had no idea that there was this connection to looking at non-agricultural societies.