Renaming a Domain

I work at a small school with a network consisting of one Domain Controller running Windows 2003, no exchange and about 80 users. We need to change our domain name by either doing a rename or by setting up a new server and migrating over users and group policies etc. Does anyone have any opinions on which option would be better? I know neither is going to be easy but I would think that renaming would be easier on a smaller network. Is there any 3rd party software that would help if we go the migration route?

Any input would be appreciated
Thanks
Tim Schmidt