That's the expected behavior. It can take up to 36 hours to automatically get an update. The only way to force it is to enter/exit the channel store, as you noted. If that works, then you've done everything correctly, and you either need to inform your users, or just wait a day.
My Channels: http://roku.permanence.com - Twitter: @TheEndlessDev
Instant Watch Browser (NetflixIWB), Aquarium Screensaver (AQUARIUM), Clever Clocks Screensaver (CLEVERCLOCKS), iTunes Podcasts (ITPC), My Channels (MYCHANNELS)