But the lense through which we have to judge the constitutionality of any measure rests on criteria like:
-is this an enumerated right; is this an unenumerated but recognized right; or is this an unenumerated and as yet unrecognized right
-whether or not the right is 'fundamental to the concept of ordered liberty'
-what level of judicial review do infringements of this right fall under (rational basis, intermediate, or strict)
The right to travel isn't explicitly spelled out in the Constitution (it was in the Articles of Confederation, though.) However, it has been recognized- Saenz v Roe, US v Guest, Shapiro v Thompson. In Shapiro, it was called "a virtually unconditional personal right". I'd say that qualifies as fundamental. Shapiro also set out the strict scrutiny standard for review of this right.
So now we get to the meat. Does government not giving you the green light to fly, via private carrier, infringe on the right to travel, and if so, would those restrictions pass muster under the strict scrutiny doctrine of judicial review.
One way of looking at it would ask whether or not the restriction is wholly of the government's action. In order for a private carrier to get protected status under FAA regulations, they agree to follow the government's directives regarding security. Nobody forces a private carrier to do so, but all large airlines do. Therefore it's the carriers who are denying you boarding, not the government- even though it was the government's refusal to give you the green light that caused the carrier to refuse boarding. In this approach, it is the action of a private company, not the government, that prevents you from traveling via private carrier. If it isn't government action, no right can be asserted- private companies have wide latitude to deny you service for whatever criteria they wish. Barring discriminatory practices, all are legal. No need to go into strict scrutiny. Additionally, these regulations only prohibit travel by certain carriers, not all, so the scope of the infringement is limited. ie, the government isn't prohibiting you from traveling by air, it's prohibiting a person from traveling by air via certain carriers.
Another way of looking at it is not judging based on the entity doing the refusal, but the basis on which you are refused. In this light, government is the entity ultimately responsible for your inability to board a commercial aircraft. You wish to contract for services with a private company, and the government is blocking that. It affects your right to travel via the most efficient means. So let's look at this infringement via strict scrutiny.
Strict scrutiny has three legs:
-must have a 'compelling government interest'- something necessary or crucial, not something like a vague 'promote the welfare'.
-must be narrowly focused
-must be the least restrictive means to achieve the goal
The compelling government interest would be preventing the death or kidnapping of passengers on a commercial airline. Where I have real trouble is the 'narrowly focused' bit. Can something so error prone, that the government admits includes incomplete and incorrect information- can that be said to be narrowly focused? Doubtful, considering that the government also admits that some people who meet these same criteria are not on the list for fear of letting them know they are under investigation. Since all three legs of the test have to pass, we don't even need to look at the 'least restrictive' leg.
I can't make a similar what-if for denying firearms for people on the supah sekrit terra lists that would lead to the conclusion that such measures constitutional. Due process clobbers it every time. Especially not in the eight states that also regulate private sales.
eta: Some good reading-
http://www.fas.org/sgp/crs/RL32664.pdf, http://216.197.126.193/inthecourts/detail.cfm?id=274