I often stream videos through Air Video to my iPhone then airplay it to my apple tv. AdrianK is right about the streaming to iPhone then airplaying to apple tv; but in my experience, airplaying it to the apple tv is just as fast as watching it on the iPhone.
If you want to stream videos from Air Video straight to the apple tv you can use an app called AirFlick.
http://ericasadun.com/ftp/AirPlay/
It integrates the airvideo server so you can live convert as it streams to the apple tv. It works very well but you have to be at the computer to choose the video so it is not as convenient. You can also airplay music, pictures, pdfs, etc. with the app too.