I am a Brit, living and working in the US with a Green Card. I have been flying DC10s for a US cargo airline before, during and after Sept 11th. Even though I was furloughed for 3 months at the beginning of 2002, I did not need to go through the foreigners' background check when I was recalled.
I have since been hired by Air Tran to start training in January. In order to be hired there I had to go through the check. It is very simple. I was mailed an 'authorization to release information' form to sign by Air Tran, who then forwarded it to the US Dept Of Justice. The check can take up to 45 days. Mine took only 10 days and I was cleared to start training.
It is my understanding that if you are not grandfathered in (ie: you were not trained on an aircraft weighing more than 12,500lbs before the regulation came into effect), you cannot commence training at this time.
For the record, in 5 years of airline flying in the United States, I have never experienced any animosity in the cockpit due to the fact that I am a foreigner flying in the US.