Everybody seems to agree that we have to get rid of the cons, if for different reasons.
Guy Steele proposes an incremental extension, the conc, with an eye towards losing the accumulator idiom, and emphasizing divide-and-conquer. Alexei Alexandrescu proposes the radical range, for enhanced generic algorithm programming and general awesomeness. Dylan, Goo, and PLOT have stepper-based iteration protocols, that were designed so that the compiler can erase them in some cases. Oleg proposes a left-fold operator with premature termination as the best collection API, and turns it inside-out if a stream-based interface is needed. Clojure uses the cons's first/rest interface as the generic interface for all sequences, which is kinda unbelievable.
The jury is still out, but I think ranges are the most interesting solution for stateful languages, whereas conc lists seem to have their charms in a poorly applicable, I mean, purely applicative setting. Oleg's API probably only works for people with a brain the size of Oleg's.