Honestly, I've never used an Apple TV that didn't lag (and I own three). It's just the nature of the device.
I suppose a better description would be the Apple TV is slow to respond to remote commands. If you get too far deep into its menus and press the menu button on the remote quickly, chances are you're going to have issues as it tries to get back to the home menu.
Generally, after a few seconds I get two or three beeps in a row and then it finally goes back to where I want it to go.
Apple needs to update it with more RAM and a faster processor.
Thats the general feeling I've been getting from it.
Would be better with an Atom processor in it and 512mb as apposed to the 256(?)