I think multiple approaches to this would work. Those single-sentence "tip of the day" type tips during loading (contrary to Garulon I do think people read this, at least some of them do, occasionally, by accident, and that's already a win), that video during the first startup, and maybe something akin to the bouncing start arrow in Windows 95 ("move your mouse into these corners!" "swipe in from the sides!") the first bunch of times Windows has started/gets unlocked. You'd get people up to speed soon enough.
Also, I think we as geeks vastly underestimate normal people. I've seen plenty of normal people who didn't struggle for a second pulling down Android's notification area thing (whatever that is called) even though there's no visual cue for it whatsoever. Also, everybody and their gran has somehow managed to get to grips with an iPad despite their only experience with computing devices being an outdated version of Windows.