I've been experiencing the same issues as simcy. It was working great for many months, than in the past month it's started to act up. Typically I need to restart the Air Video server daily, and when I try to load videos on my AppleTV they take about 2 minutes to load before they start playing. Once they start playing it seems to be fine. Oddly, if I use my iPhone or iPad, they play without issue.
One thing I've noted in my configuration, it's a wireless PC that is running the Air Video server that regularly needs restarts and slowly loads the videos for my AppleTV. If I run the Air Video server on a PCI that is wired into my router I don't experience any of the issues I've listed. FYI, my Apple TV is also wireless. Tried many restarts of my AppleTV with no resolution.
So it looks like this:
Air Video Server --> Wi-Fi --> Router --> Wi-Fi --> Apple TV = Problems
Air Video Server --> Wi-Fi --> Router --> Wi-Fi --> iPad/iPhone = OK
Air Video Server --> Wired --> Router --> Wi-Fi --> Apple TV = OK
Air Video Server --> Wired --> Router --> Wi-Fi --> iPad/iPhone = OK
Update: It appears that all of my issues with AirVideo were specifically related to my router. I replace my D-Link router with a newer ASUS AC1200 and everything has been working flawlessly for the last few days.