I liked the storyline very much although it was rather short (maybe 13-15 hours). Luckily, the game has some decent replay value with all the side quests, hunting for collectibles, and co-op. If you loved the previous Fable games then I'm sure you'll love this one just a wee bit more.
The combat was changed slightly but overall remained relatively the same. We did get some cool battle animations from your character (ie: parry + counter on a balverine would make the balverine jump in the air and you pierce the heart w/ your sword or you would perform a vertical scissor kick in mid-air.)
Magic abilities were changed as well. We can dual cast spells now if you weren't already aware of that (although it has to be unlocked). They removed Raise Dead and Time Slow and changed them into potions.
There is no level up system (which I thought was odd but this new system works just as well). You acquire guild seals which will get you all the traits/skills/powers you desire to use.
PS:
I love the gnomes. They are hilarious.