The 4.0.4 update provides some partial relief. My ATV is set to auto update apps, but didn't, so I had to do it manually.
The newer version does make the channel grid usable again, and initially, it was even as fast as before, but for whatever reason, has slowed down a bit since first updated, though it's still faster than 4.0.3. I've seen the suggestion that toggling between the All and Favorite channel lineups may play a role, but can't confirm that.
But if nothing else, it restores the right-edge quick scroll that was completely broken recently.
Unfortunately, the main menu screen is still slow as molasses.
The developer has obviously been playing with a lot of the code, and jacked a lot of it up. In addition to the poor responses, the Menu button was acting inconsistently, and there are still odd blank screen interludes that weren't present before.
Fundamentally, I think they may have intentionally tried to alter the touch UI responses with the grid, and change the scrolling action from having inertia, and being flickable, to scrolling based on a constant touch motion, where it stops quickly if contact is lost. The former seems more responsive, but isn't as precise as the latter.
Keeping a finger on the touch pad while motioning does make the recent versions more usable, but isn't as fast as the old method for jumping quickly to a different part of the grid.
Of course, AT&T being AT&T, all of this could be unintentional and just their standard MO of incompetence.