Taking the batteries out works. I first tried reinstalling in 30 seconds and then a few hours and it didn't work. Then I just left them out overnight and reinstalled the next day (~10 hours) which worked.
My guess is that the remote had its firmware updated (hence the flashing green light vs no light that would mean the firmware crashed) and to fully install the update, the remote needed to be cold-booted. The overnight thing could be a large capacitor that keeps the remote running so as to save the batteries. You want the remote to be always on so it responds as soon as you pick it up and press a button, hence the capacitor. The only way to do a cold-boot on the remote is to completely power down its circuitry by leaving the batteries out for an extended period of time. The amount of time that worked for me was about 10 hours.
I had also previously rebooted (system restart under settings) the Roku unit itself, and performed a cold-boot (unplugging for 30+ seconds) so there is no real way of telling if this played into the working formula. Perhaps someone else can just do the cold-boot on the remote (taking the batts out overnight) to ascertain the problem is localized to the remote itself.
