I've been wondering if Lisp without cons cells, or at least with cons cells deemphasized, would work better than Common Lisp. Vectors work better than linked lists with architectures like ia64, have better cache locality, and admit more parallelism in loads (increasingly important as memory bandwidth grows faster than memory latency shrinks.) Algorithms on vectors are often asymptotically faster than algorithms on lists; as computers become faster and the problems addressed become larger this becomes more, not less, important.
Vectors could be allocated with some extra unused space after them. This way, they could be expanded (by a factor of 2, say) without having to be moved. With this, vectors could be incrementally expanded at the tail in constant amortized time per operation. The distinctive features of Lisp, such as macros, could survive mostly unchanged.