Clean install of Yosemite on 2008 MacBook Air
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