ThornyCactus,
It is not that the schools/CFI thinks that you are a terrorists because you are not an US citizen. The bigger problem is the limitation of H1B seats and the the eligibility requirements for the same.
1) There are only 65,000 H1Bs every year. And that includes all the IT, Medical, Education folks as well. Every year hundreds of thousands of people apply for work authorisation visa. This year, they are anticipating to reach 65000 application by April 2nd (the visas are awarded in October). So this year USCIS has decided to go with the lottery system. So everyone has an equal chance.
2) The USCIS does not recognise the CFI job as requiring H1b. Remember the school will have to advertise for an American before they can sponsor for visa.
3) All applicants for H1B must be at least undergraduates or hold an equivalent undergraduate doploma.
4) To do all the paper work, schools will have to hire lawyer, advertise in the local news papers and then go through the motions. All this takes about 6 months of preparation and anywhere between 4-10 thousand US$.
Now you tell me, why would a school go through all the hassle and spend all this cash when they can wait for a few months and hope to hire a local CFI!!!!!