The Matrix library doesn't have to have knowledge of type Foo. Matrix<Foo> will be instantiated when the application is built. All of that works fine-- yes, even with dynamically linked libraries. Let's not forget, libstdc++ is a dynamically linked library itself, and it's stuffed full of templates.
The problems start when you try to deal with versioning. Basically, templates make creating any kind of backwards-compatible API much harder. This is one reason why the libstdc++ std::string still uses a reference-counted implementation, despite the fact that it's known to be slow on modern multi-threaded machines. Changing std::string (otherwise known as std::basic_string <char, traits, alloc>) would just break too many things.