What method are you using to show eligibility? I entered the country on an H-1B and have applied for a green card through the labor certification route. Heres my timetable:
Nov 1998 (yep, 5 years ago): submit labor certification forms.
Oct 2000: my company got the OK to advertise my position and file Notice of Job Opportunity.
Dec 2000: filed final documents for Alien Employment Certification.
March 2001: received Alien Employment Certification. File Immigrant Visa Petition.
Sep 2001: something else happened that was a much more major event to thousands of people, so I shouldn’t complain, but it buggered up the speed of the immigration process.
Feb 2002: Immigrant Visa Petition Approved.
Mar 2002: Green Card applied for (I-485).
Apr 2002: notified by INS to expect I-485 to take 650 - 725 days to process.
Apr 2003: was fingerprinted.
Aug 2003: my lawyers said applications were now taking 2.5 - 3 years, as opposed to the 650 - 725 days previously indicated.
Best of luck.
(And on preview I have just read C3’s story, which has made me even more depressed.)