They tried to run a "trace route" and they cannot locate it. It's now being "researched" by the lost and found dept. I think it's lost and found its way into someone's trunk.
I called Apple and they were very supportive and helpful. We'll see how much so if it is confirmed "lost" by FedEx.
Apple is definitely very good about handling lost/mis-delivered packages, both for purchases and for repairs. My iPhone that was sent back from the repair depot somehow ended up in Louisiana, and after maybe two calls with Apple (one to them, one back from them) they had a brand new iPhone on my way - they make sure they had all the necessary information, so that they could be the ones to entirely handle the situation, and the new iPhone was shipped out that same day.
Just make sure to stay on them and they should get you squared away - of course the problem in this situation is that the Air is in short supply. If this was say, for a normal MacBook, there'd be a new one on the way to you immediately. The air... not so much. =(