It sounds like the USB drive doesn't have the drivers to boot the other macs. :-(
The fastest path forward is to simply erase install a basic Snow Leopard OS onto the failed macs. While this is happening, do download the 10.6.8 Combo update to your USB drive just in case it's needed.
Don't bother running the updates unless the Lion installer forces you to get to a higher version than your 10.6 installer delivered.
Once you boot into Snow Leopard - you can try again to mount the USB and execute the Lion upgrade package. I don't know if it runs well from the USB or needs to be copied to the internal boot drive.
There's a little uncertainty in my brain - so I don't want to write too much without making sure this makes sense to you.
As an alternative - you could try instead to transfer the recovery partition, but this may not be universal (include the drivers the older macs) either.
There is a step-by-step recipe here for copying any bootable volume to one file on a USB drive.
If you are curious or feel it's worth a shot, image the recovery partition from your Lion mac.
You should be able to boot from DVD and use disk utility to make an equivalent partition on the "non bootable" mac and drop the recovery data to get a minimal bootable system and avoid a full Snow Leopard install.
Unless you are familiar with Disk Utility and the steps to capture, the reinstall option might be more likely to succeed on first attempt. I certainly don't know if this partition is customized by Lion and not universal so I've made it an aside for the curious.
What you're encountering is not related to the pre-existing version, but likely that your MacBook Air is not supported for Yosemite at all. Apple lists the Late 2008 model as the earliest MacBook Air which can run Yosemite.
(Source) http://support.apple.com/en-us/HT6412
Best Answer
Unless your models are Early for the years, they should be supported.
Apple requires you to have 10.6.8 or newer running since that's where the Mac App Store runs. If you have access to any Mac running 10.6.8 or newer, you could sign in to the App Store and download the 10.11 installer. It has a script to make a bootable USB installer - one shot command:
If you run into issues, this thread has several other methods to work through fixing your installer.
If you're not seeing the USB drive or network boot, perhaps resetting the NVRAM might help with that.