I am not totally sure about that. Maybe they have to login.
I'll create another test account and see what happens then. Another interest point (sort of) - For the 'Original User Group (for promotion to run)' should I set the groups to all (inc. Admins, Mods)?
Users do not have to log in, the promotions task will promote them. Check the promotions log to see if the user was promoted or not, if not double check your promotion settings.