Does the new MBA use a different DVI adaptor than the old models? Is it a 'mini' to 'micro' situation?
It uses a Mini DisplayPort video out, thus you either need a MDP to VGA or MDP to DVI adapter. Mini DisplayPort to DVI Adapter Mini DisplayPort to VGA Adapter