So far I've had one good experience with naturalization records. I had a photocopy of my grandfather's naturalization certificate and easily obtained a copy of the declaration from the county clerk. I have just found out that Salt Lake has a hundreds of films of naturalization information and they are, at least for New York, indexed, so I'm going to try there for other lines.