I didn't think I could make this work, but I tested it and my original rule spammed the snot out of my mailbox (something like 32 e-mails in 10 seconds). Here's how I did it, though I also see there is a SystemReboot event class that might work for this even better. The LEM always has a dozen ways to skin any particular cat, so this is just "an" solution, not the "only" solution. In fact, I think I may have gone a little nuts trying to demonstrate multiple possible correlations that might catch these events.
The many "NOTS" are because when you reboot a system, Windows goes insane with activity and you only want the actual user, not the many system accounts that get involved (this is what spammed me originally, and the NOTS reduce the spam)
I have one correlation group looking for an Agent going off-line and then on-line, which usually means a reboot, but could also capture a hard power-cycle. The SystemReboot would only capture nice shutdowns.