I think the chief reason line length is considered noise rather than signal is because it's so unpredictable. When it's known, people do a great deal to minimize their time spent in line. They go to the store at off hours; they switch lines once they're standing in them. I know my local Taco Bell gets a lot more business from me because of their speedy response time, vs. the teriyaki place next door that I like more, but takes forever. And my college's bookstore has had a great deal of success with putting live camera feeds of their lines (or lack thereof) on their website.
But with grocery stores, I couldn't really tell you which of the two grocery stores in my area would have a longer line. They're about the same, and that's close enough.
So you'd need a pretty big delta for line length to become a differentiating factor between stores. The current system of a cashier scanning items individually probably won't see drastic efficiency improvements without drastic changes, so...drastic changes are needed.
After a certain point, changes in "line length" become "presence or absence of a line at all." As jonnathanson says below, electronic scan-as-you-buy is probably the future there(Smith's, in answer to my cousin's email inquiry, mentioned they were testing a portable bar code scanner). I'm under the impression that grocery stores have pretty cruddy margins, so maybe I shouldn't read that much into "in testing." If anyone out there is dying for a startup idea, I think this one is worth a look. (Before you say it, I'm working on another project, and my cousin left for grad school.)
Since few things are more self-satisfying than sailing out of a store without waiting in line, maybe Whole Foods will be the first? ;)
If every grocery store in town has the same expected line length, then the entire cost of line length is borne by the consumer---since the line lengths are in equilibrium, none of the stores feel economic pressure to reduce their line length, and the line length is a fixed cost of food shopping (unless latency becomes comparable with the length of time a store is open during the day, in which case it's actually limiting the number of customers they can process per day, but I find this highly unlikely).
Granted, a store might try to differentiate itself by reducing its average line length, but there are many other (perhaps more important) factors that go into a consumer's choice regarding grocery stores, e.g., Wal-Mart mega-food-store competes on prices, Whole Foods competes on its customers' self-satisfaction (I kid, I love Whole Foods).
Intuitively, it feels like grocery store line length is in the noise when considering the decision process for most consumers, especially since I can get zero line length at almost any store by going during off-hours. If it's in the noise, there's no selection pressure to improve it.