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