It’s so easy to miss… Your ancestor claimed to be from Luxembourg. Yet, you can’t find their hometown anywhere in modern Luxembourg. What’s going on?
It may actually be in Belgium. What is now the province of Luxembourg in Belgium was split off from the Grand Duchy in the 1830s. An American immigrant arriving in the 1860s very well could have been born in the province of Luxembourg before the partition. Read more about the split in this fascinating Wikipedia article.