Census takers spelled names as they heard them. This link (https://familysearch.org/pal:/MM9.1.1/VNK7-438
) shows the family in the 1875 NY State census. This time the census taker spelled the name Schutt. But Frederick is listed as "Fritz."
Borders in what we call Germany changed many times over time. They were a bunch of small Principalities. Prussia was one of the largest Principalities.