The universal distribution of ubiquitin among eukaryotes strongly implies that it is necessary for eukaryotic existence, does it not?
It implies that our Eukaryotes require it, yes, but it doesn't imply that life like a Eukaryote requires it. There's no reason to think that we couldn't engineer a Eukaryote so that it used a different molecule in place of ubiquitin, it'd just need every protein that interacts with it to be re-worked - which is why evolution can't do it.
Ubiquitin is a signalling molecule, not an enzyme, it's functionality lies in its interaction with other proteins, not it anything inherent to its structure (well, it needs to be small, easily synthesized and capable of being combined into chains but that leaves literally thousands of possibilities).