Some possibilities to explore:
To locate immigration/naturalization records, try the USCIS Genealogy Program: http://www.uscis.gov/genealogy
(but be aware that there's a charge for each search of their records)
If you aren't already familiar with JewishGen (http://www.jewishgen.org/
), check out their resources, especially the discussion mailing lists. Post your questions on those; more researchers will see them.
Also see if you can locate NYC birth/marriage/death records via the tools at http://stevemorse.org/
. For the time period of interest, you may be able to obtain copies from LDS microfilms.
Do you have any information about the Hebrew names of the people you're researching? They may have arrived in the US using some variant of their Hebrew names, rather than the Americanized names later used.