Changing Domain and Server names in AD?

A company that I just started working with has a big problem. I inherited the mess, and now I need to fix it because it is causing some problems.

The last admin used underscores (“_”) in naming some of the servers and the domain.
Example: “Domain_Name”

I know I am going to have to jump through hoops and will loose some stuff.
Windows 2000 AD domain, Exchange 5.5, IIS 5.0, about 50 clients/workstations, 10 servers, etc…

What is my “best” course of action?
What will I have to do over?
What exactly will be effected?