Is the Macbook Air always in the same physical location? If so, then it could be an adjacent device that is throwing out 2.4GHz interference. This could be a poorly shielded USB3 device, hub or cable. Or a WiFi base station.
You could try Safe mode, to see if there is software interfering
<http://support.apple.com/kb/ht1564>
What happens if you turn off your Macbook Air's WiFi? WiFi and Bluetooth often share the same antenna's in a Mac. This is an experiment, NOT a solution.
Have you tried any of these devices with a different Bluetooth source, such as your iPhone, iPad, etc... Do they behave the same? Do they behave the same if you put your iPhone next to your Macbook Air?