CAVU:
It sounds like you are involved in a Catch 22 situation. I presume that you have showed your letter saying that security clearance is available to the prospective employer?
Could they not then hire you on probation until such security clearance is obtained? It sounds like there is a bit of post-911 overreaction afoot.
Good Luck.