Thanks RT... it's funny, I actually found those records in the Wittring TDs in the meantime before I saw your message. I had some clues to look there and considering the proximity, I gave it a shot.
I think there's a chance this could be the Jean Nicolas I'm looking for. The one I am looking for did come to NY in 1832 and died in Illinois in 1881. I don't know if all of those children belong to the same parents or not because I can't view the actual birth records - it's possible that the duplicate annes or nicolases belong to another set of parents in that town.
The Geneanet trees are useful, I've been looking at some on ancestry and familyseach.org as well. Most of them have that other information I gave about being born in Herbitzheim - not sure where that originally came from.
Thanks for your help, I will continue digging.