AD upgrade/refresh - what would you do?

We're a small single site organisation of around 600 users. We have an initiative in the works to refresh/upgrade our ageing AD infrastructure (we still have AD 2003 domains!!!).

We have an opportunity to do things the right way - we have an historic mess within the AD (OU's, groups, users, accounts, policies, etc.) are are all in a bit of a state.

What would you do? Would you....

a) Start a fresh new domain from scratch and migrate.... or

b) Upgrade the AD 2003 and "fix" all the problems (if so, how would you go about it)