Why is it illegal in Europe? Klout analyses your Twitter interactions which are publicly visible.
So if you have a twitter account, they can generate a score for the twitter user using publicly available information and then if you sign up to klout, link these existing calculations to the newly created account.