Ditto on the VLC recommendation. It's free and plays almost anything.
You can also try installing Perian
http://perian.en.softonic.com/mac
which is a free set of plugins for QuickTime giving it the ability to playback most HD CODECS.
Another possibility is your MacBook Air may just not be able to playback higher res HD. The first generation of Airs started with a 1.6GHz Core2Duo going to a 1280 x 800 display, which isn't going to do 1080p MPEG4 playback.
Wamphryi's recommendation to "Buy a PC" rarely solves problems with HD playback. As a professional system configurator to the television and motion picture production industry in Los Angeles, I can tell you that PC systems are always the hard ones to solve workflow problems with. The US video industry revolves around Mac computers, and the FCC and Motion Picture Group standards. Anything else is a workaround.
Wamphryi is correct though, in that Apple does severely limit iTunes' file compatibility, and is even more restricting w/ iOS playback. If you're trying to playback your file using iTunes, stop and use something else. If you need iTunes so you can move your video to an iOS device, you'll first need to transcode the video into a compatible file. Handbrake is a great free little app that can help you do just that.
http://handbrake.fr/downloads.php
Good luck.