Too many possibilities.
Could be frame rate issues - if the original file was at 25 or 29.97 fps (frames per second) and it was converted at 23.976 - it will look like it has a regular stutter. Solution: open file in quicktime, go to the movie inspector, manually set visualhub to convert at that framerate.
Could be networking issues - start any show or movie and if you're (for example - could be many causes) wireless G, you may see the show start and then pause for a few seconds, stuttering if you quickly chapter forward to a random point. Solution: go wired, set up a wireless N network, or pause movie or show for a few extra seconds before trying to watch it.
Could be a movie pushing the appletv to it's limits - 720p movies can be fine, but regardless of what the manual says, it is possible to convert 720p shows at 25 fps or higher and have them be fully compatible, but if so, they may stutter depending on file complexity (ie processing power required by the appletv).
Hope that helps somewhat!
N....