As Mike mentioned, the promotion cron is only applied hourly, so that's the sort of time frame for this to occur for active users. However if users aren't active (ie they haven't visited the site for a little while), the promotion changes for them won't occur until they next visit the site. The only way around this is for you to rebuild the user group promotions cache in the ACP.