This may not apply in your case, but a lot depends on how you know they arrived at Ellis Island. I "knew" that my paternal grandfather, who died long before I was born, immigrated from France to Ellis Island. I don't know if I had ever actually been told this, or if I had just always assumed it because my grandparents lived in Paris before coming to this country, and my father was born in New York. I could never find my grandfather at Ellis island, though, no matter what search techniques I tried. Eventually, with the help of someone much more experienced than I was, I learned that the reason I couldn't find him was that he sailed from Liverpool, not Le Havre, and landed in Philadelphia, not New York.
So, unless you have other documents, such as naturalization papers, that indicate a New York arrival, try expanding your search to other ports of entry. Good luck!
Deborah Blankenberg (JewishGen ID #613395)
Researching BLOCH/BLOCK (Germany to New York, Colombia and Missouri), BLINDER (Kishinev to New York via Poland? and Paris), KUSHER/KUSZER (Lodz vicinity to New York via Paris), GOLDSCHMIDT (Germany)