It sounds like the law was changed without a lot of forethought, but there seem to be options - that Permanent Residence path may not be easy, but it does appear to be an option.
I don't really know what to think. I don't even know what the law is for Americans born abroad, not on a military base like John McCain.