Resolution (of sorts): While I have no idea what the problem was, randomly plugging and unplugging USB devices before and after using the wireless receiver broke whatever logjam existed. After firing up a new iPod shuffle for the first time, suddenly the wireless works again. So, if you have this problem, I guess I recommend you buy yourself a new iPod shuffle. Worked for me.