But does Common Lisp allow multiple implementations of those data structures to exist in the same program actually allowing programmers to utilize the best tool for the job?
If you mean can users extend the core CL data-types, no, but you have a wealth of tools to do that yourself; use generic functions to implement whatever interface you wish, then provide for specific implementations.
That's the problem. With Clojure you don't have to invent interfaces and then convince other libraries to use them. All the data structures are built upon well considered language level protocols that anyone can implement preventing pointless API proliferation.
Personally, I slightly prefer Clojure over SBCL.