Brian Marick has a stellar post that contains his talking points for bringing Agile into a legacy code base that really needs some cleaning up.
Go ahead and read it now... I'll wait.
His points are very valid and well stated. Specific points that rang true for me were having the programmers read Working Effectively with Legacy Code. I recently purchased this book and have started reading it. The concepts presented in there are very valuable and easy to implement.
Ron Jeffries's analogy is completely on par. There are many times that Ive looked at some projects and thought to myself, "how will I ever get sufficient test coverage on this monster?". The trick is to not do everything at once, but rather each time you visit the code, leave it a little nicer than you found it.