Wendy,

Did he naturalize?  Sometimes a name change occurred at time of naturalization, and was noted on the nat papers.

I believe that many people that chose to change their names did not bother with any paperwork though.

But, there are records of name changes in NY.
http://www.archives.nysed.gov/research/res_topics_gen_naturalization_name
"The court order changing a personal name is recorded in the county clerk's office in the county where the person resides."

Regards,

Sherri Bobish
Princeton, NJ