personally I haven't seen nationality get in the way. Actually, I've seen many folks that are either 1st or 2nd generation US citizens. But the rest of what you say is right, though not all clearances require a polygraph. Relatively few people get those if you include regular Secret and Public Trust positions.

Wikipedia has a decent breakdown of the various clearances btw: http://en.wikipedia.org/wiki/Security_clearance