I have a 5 and 3 year old and watching them patiently page through the instructions and put together something complex that they really care about is incredibly satisfying. Some of the sets have relatively complex mechanisms in them as well (I'm thinking specifically of the Lego Friends Shopping Mall and the Minecraft sets) and the kids are forced to understand them at least on some level.
I don't know that my daughter would be interested in classic Legos, it's Lego Friends that caught her and will keep her in front of a 200 page instruction manual for 4 hours and in my mind there's nothing wrong with that.