Yeah...what JoostinOnline says.
I understand your reaction of "deleting everything and starting anew", but that's actually far more risky than just starting from scratch and overwriting the semi-softmodded things.
Priiloader in particular is a tough one. Put briefly, it copies the system menu to another memory location, then literally installs itself over the original system menu (since the system menu is the first thing to load*, this is the only way to load something other than the actual wii menu if you want).
Now...priiloader itself can enable some important hacks (like region free'ing everything), but it mostly works in the background. And it can be set to run something automatically when your wii starts (this can be the wii menu but also the HBC, bootmii or even homebrew). Going by the error message, that's still the system menu (I'd say keep it like that until you're comfortable with how things work).
Now...in case you're wondering what IOS and stub mean...
An IOS is the underlying code for input and output of basic things like wiimote controllers. It can be compared to the BIOS in your computer, but with one important difference: the wii has many IOS'es by default, and there are empty slots which aren't officially used. Unofficially, it's a different story. Slots above 200, for example, are never used by any game, but is traditionally used when hacking a wii. Probably all softmodding guides have you install something to slot 249 (unfortunately, it traditionally tends to get called "cIOS249" of even "IOS249" rather than the actual version you're installing**).
Of course, nintendo knows about this practice and have something you could call a countermeasure. Firmware updates on a wii are barely more than updates to a certain number of IOS'es. And since no games use slot 249, nintendo distributes an IOS249 with pretty much no code whatsoever. This is what's called a "stub". Its sole purpose is to overwrite the cIOS you installed from the guide you followed.
I haven't watched the youtube video (I tend to avoid these, though I must credit that this one is both recent and uses modmii, so it could've been much worse). But what I think has happened is one of two things:
1) you could install priiloader and somehow set it to force IOS249 as the main IOS to use for the system menu (all programs, be it channels, wii iso's or the system menu, need an IOS to work. It's the only thing that works in the background). Either you couldn't install that IOS, or you did and it got overwritten by a firmware update. End result is this message. And JoostinOnline's mention will fix it.
2) you attempted to update the system menu and some IOS'es manually. As said, the system menu needs a (non-stubbed) IOS to work. Now with each firmware update, nintendo tends to install a system menu that uses a higher IOS number (60 for 4.1, 70 for 4.2 and 80 for 4.3 IIRC***), and stubs the previous ones. As such, you need a system menu and the correct corresponding IOS. If you know what firmware you're on, it's best to do the following:
2.1: use modmii to download the latest non-stub version of the IOS in wad form and put it on your SD card (if you don't, just download 60, 70 and 80...it won't hurt)
2.2: use priiloader to load into the HBC
2.3: use MMM (or whatever wad-installer the youtube channel recommends) to install this wad (or wads)
That should do it.
Can't say I know a better guide. I always recommend modmii. If you ask me, it strikes the best balance in giving the right kind of information with the most up-to-date files. My guess is that the youtube-video just follows modmii, so it should be fine. I know things are a bit technical, but the learning curve isn't as steep as it used to be.
Good luck.
*okay, this isn't entirely true (there's this whole boot sequence in front of it). But for now, it'll do
**this is kind of like referring to your car by where it's parked.
***please don't quote me on these numbers; if I'm wrong, I hope someone can correct me. But I'm sticking with it for now to get the point across checked...the numbers are correct
EDIT: damn...almost forgot to mention the first thing I wanted to say. erm...look: the thread title is you asking to remove priiloader. But in this situation, priiloader is actually the only thing that prevents your wii from being fully bricked. It's your wii, but if I were you, I really WOULDN'T uninstall priiloader. Good guides strongly recommend installing bootmii and priiloader especially for cases like this. Removing it would be like a mountain climber cutting the safety rope and hoping for the best.
