Thanks, Bilalakhtar! After posting, I tried the Fastboot option on the air unit to no avail. Problems were similar as stated in here:
Using “adb kill-server” didn’t help. What worked in the end (for me) was installing Zadig USB drivers. I’m guessing the clockworkmod drivers mentioned by Andrew Bostaph in the above post would have worked as well.
And as predicted, once the firmware matched between units, I was able to pair the devices without any trouble.