I really liked M&B. Is Warband different enough to play all the way through it again? From the description it doesn't sound like they changed that much.
its actually changed quite a bit in the non-combat aspects such as much more economy based gameplay with be able to buy and run your own businesses and some other aspects. plus this complete version also includes the soon to be released fire and sword.