Blob is indeed a primitive data type:
Contains methods for the Blob primitive data type.
And List.sort allows you to sort primitives:
Using this method, you can sort primitive types, SelectOption elements, and sObjects (standard objects and custom objects).
However, the documentation is often wrong with respect to built-in objects, mostly because built-in objects are pseudo-classes. I call them pseudo-classes because they don't follow the normal rules that classes do in Java, and many of them don't behave as you'd expect if you actually read the documentation.
As an example, you can only use the for-each loop on Iterable objects (those that implement the Iterable interface, which returns an Iterator object, one that implements the Iterator interface). The documentation implies this when you read up on custom iterables. You can call iterator() on a Set, and you can use it in a for-each loop, which means that it does, technically, implement the Iterable interface. So, you should reasonably be able to use a Set in
However, if you've ever tried this, you'll find that Set doesn't implement Iterable, meaning you can't actually use it in
String.join, despite the fact that it works in for-each loops, and has a function that returns an iterator. This actually prompted me to post an idea. This same behavior also thwarts attempts to write utility methods that can accept either Sets or Lists as Iterables, since Sets don't technically do so, but you could accept an Iterator argument and use that instead...
I read an interesting article about how Apex Code is actually an interpreter that acts as an intermediary to the underlying JVM that salesforce.com runs on. What this means is that there are many constructs that simply aren't written into Apex Code that should probably reasonably be there, and again, built-ins and primitives are basically pseudo-classes that look like real objects until you start to look too closely. While Apex Code does work most of the time, there's plenty of edge cases where this isn't true, and the documentation doesn't cover edge cases very well.
In summation, when you find a bug like this, you have to work around it. I'd probably suggest storing all your blobs as hex strings and comparing those in memory. It'll only cost you double the size of the blob to store it as hex strings, but at least they'll sort properly. I'd also suggest filing a bug against the documentation using the Feedback option.