I've used them a couple of times in the past. The problem I see is that they don't really change that much from the time you turn them on. So even though the playlist is technically "randomized," the "Power Rock" playlist will still play the same songs everytime you start it, just in a slightly differ order.
That said the playlists aren't bad. Everything in one fits well together. I'd say they make better playlists than I would, but I'm not very good at making playlists.
Genius playlists is basically Pandora but confined to your iTunes library. Not very useful overall, but it does what it's supposed to do.