UPDATE: I fixed it, somehow.
I think the Homebrew Browser saved me. First I grabbed the "FCE Ultra GX Channel Installer 1.3" and installed it to my SD card. Then I started up Homebrew Browser, and went to its "View Installed Apps" menu. It showed a little yellow question mark next to the FCEU Channel Installer. I let it run its "Update", and then I went back to HBC and ran the FCEU Channel Installer again. It detected that the channel was already installed, and when I clicked "Uninstall", it worked this time! I also did verify that the question mark in the Wii System Menu also went away!
Hopefully this will help someone, someday.
I'd say be careful about the updates in the Homebrew Browser though; they are out of date for a lot of the other apps I use, like WiiMC, sysCheck, and Snes9XGX.