It seems fine now, downgraded to 4.1, being helped by Junkmail on IRC and following your guide (which is great).
Yet another entry into this strange, strange issue.
The error message was gone for all of 3 days, and after playing a NSMBwii hack (NSMB2 the next levels: more levels etc, edited ISO) I got the error message again. The original error message was before my aquiring said ISO. How would one go about figuring out what's wrong with my wii? I can skip the message as of now, by continuously power cycling, but it pops up randomly when starting up. I've already deleted that game's save in pure paranoia.
NOTE: I own the game NSMB wii, so I think I'm allowed to use altered game files right? from a legal/moral standpoint? A mod may correct me if I'm not allowed to talk about this here.