Your best bet is to contact your Congressman or Senator. They will be able to help.
To calrify the INS/FBI interaction; the FBI gets involved in basically two levels:
1- when you submit your fingerprints, the prints are sent electronically and check against the FBI data base. Unlike what the IIO would tell you, this process actually takes just few days from the date of fingerprints. You can verify this from several threads on this forum. Mine and my wife's were cleared in the same day.
2- the FBI also gets involved when the INS performs the IBIS check (refered to sometimes as name check). This check actuall is done from the computer terminal at the local office or the service center. The officer types in your name and birth date, and the software generates few combinations (and the sound-like) of your first and last name and your birth date. The software then checkes those combinations against the data bases of the CIA, FBI, DOS, etc... This is where the name comes from Inter-agency Background Information System (IBIS). This process takes few minutes or hours. And is generally done right before or after the interview, and the qpproval is granted if things are cleared. However, sometimes you may have a lazy or busy officer, and would do it later.
The problem comes when there is a hit on your fingerprint, or name check. It doesnot mean that you have a criminal record. It only means that the computer has a possible matched with your name (or a sound-like). In this case, the corresponding agent (FBI, CIA, DOS, etc..) will have to do a more in depth search to find out whether you are the person on their system or not. Only very few will really match. This process may take few months since the INS will NOT check on the status of the check. They will just wait to get a response (God knows when).
The only way to move the INS is through the Congressional Liason, ALIA, or a strong attorney.
So do not waste time, look up your representative, and write a polite and clear letter explaining the situation.
Good luck