Is the name "Sea Star" more accurate than "Starfish"?

It has become common in recent popularizations to suggest that echinoderms of the family Asteroidea should be given the common name "sea star" rather than the traditional "starfish". The complaint is understandable -- starfish aren't fish. In fact, humans are more closely related to fish, as they both are vertebrates while starfish are not. But is "sea star" actually a better supported name? A taxonomic analysis suggests not.

Let's consider stars, the sea, fish, and starfish.  How can we compare such diverse entities? Obviously not by molecular means. But we can return to the traditional means of cladistic characters. In this analysis I used:  1) Living 2) Primarily water 3) Non-trivial concentration of dissolved NaCl, and 4) presence of backbone.

These characters can be encoded in a PHYLIP matrix in the following manner.

    4    4
Star      0000
Fish      1111
Sea       0110
Starfish  1110

By standard parsimony this yields the following midpoint-rooted tree

So, while "starfish" is inaccurate, "sea star" is even worse!