How can I change the domain name across our WPMU network

Since 2008, we have been using the domain name: http://blogs.lincoln.ac.uk with all blogs on sub-domains. We would like to change the domain to something like http://sites.lincoln.ac.uk and redirect all requests to the blogs to the new domain.

For example:

http://joss.blogs.lincoln.ac.uk

would become

http://joss.sites.lincoln.ac.uk

and the old address would redirect to the new address.

Can anyone advise us on how this might be achieved? I guess it will need the apache web server to be re-configured as well as changes to the settings in the database.

Thanks for any advice.
Joss