Change Domain

How can I change the domain of a Drupal v5.19 site?

I have a large, existing site that I'm running at olddomain.com. What steps do I need to follow to change the site to run at newdomain.com?

I've tried emptying cache/watchdog/sessions tables, changing the domain on the hosting server and the base_url settings.php but when trying to log in, I get a server not found at "http://www.newdomain.com/?q=user/admin"

Help please.