It should take place immediately.
I would verify that the skin files exist for the site, during setup it should have copied all the folders and files from /Data/skins into /Data/Sites/[SiteID]/skins, typically SiteID will be 1
I would also look in the log for any clues. You can use the Web UI from Administratioon Menu > System Log, or access the file directly at /Data/currentlog.config
The newest errors are at the bottom. There will normally be errors logged during setup, sometimes it best to clear the log then change the skin then see if any problem was logged.
Hope it helps,