@sagitter: Like I mentioned, you might have to restart Firefox. Maybe even quit FF, remove mozilla-ublock-origin, restart and quit FF, reinstall m-u-o, and restart FF again. But with some combination of those, you should eventually be able to get the icon to display, and once it does, it should be permanent.
I've never used it before, but it seems to work fine in casual use as a replacement for mozilla-adblockplus, with a sane default configuration. (I did have to quit and restart Firefox an extra time, to get the icon to display and see the Preferences, but that's probably #1508827.)