Even though my Wii didn't automatically reboot, the process still seemed to work when I manually rebooted. I was able to go into the VC game catalog, search for my game, and it was downloadable for 0 points.
I'm on a NTSC Wii w/ Wiikey, so maybe that's why it didn't automatically reboot.