There are many articles on the web regarding this seemingly daunting task.  Today I ran into one that is by far the most complete, and easiest to follow.  Hopefully this will help you, or your clients, get the job done more easily:

http://www.windowsecurity.com/articles/Kerberos-Sharepoint-Environment.html