Been reading a few people with this problem.
Apparently if you use the Software Update to upgrade to 10.7.3, and haven't done every single patch and update to this point, you run the risk of getting this happen.
The best way of avoiding this problem si the "combo updater" that apple has made available. This does a complete update from 10.7.2 to 10.7.3 with all other patches. The file is bigger (i think 1.2gb). But nobody who's done it this way have reported this problem.
If you do use the online updater and you get the error. There are a couple fixes I've seen mentioned
Restoring from backup and doing the combo updater is probably the "easiest"
But, the other option is using your MBA in target disc mode from another mac, and installing the Combo update to your target disc moded Mac. Apparently this completely fixes it with no need to roll back.