I guess it's important to try both out for yourself, but one notable difference is that while MediaElement depends on jQuery, Video.js is completely library-independent, though you can easily use it with jQuery easily: http://videojs.com/jquery/

The jquery page hasn't made it into the new site yet, but still true.

VJS also has free CDN hosting, and is pretty easy to skin both HTML5 and Flash using just CSS. MEJS is a pretty decent project though, as are a few of the many other HTML5 video players. So not my place to say which is best, but we're working hard to make Video.js pretty great.