There are a couple gotchas on using delegation. It sounds like you are well on your way to making it work however, and you understand exactly why things worked when on localhost versus a remote client. Please note that you must be in Native domain and not Mixed for Kerberos delegation to work.
Here are complete steps for Kerberos delegation to work:
Server-side tasks:
---------------------------------------------------------------------------------
1. IIS server is member of domain
2. Set IIS server computer account in AD Users & Computers MMC as "Trusted for Delegation"
3. IIS Server must be rebooted for this policy to take effect.
4. Integrated Windows Authentication only must be selected for site / virtual directory
5. IIS must not have NTLM only set as authentication method (this is usually not a problem, NEGOTIATE is default, so unless you specifically ran a script to change this, don't worry about it).
6. IIS server name either must match exactly account name in AD, or SetSPN tool should be used in cases where IIS site is set as alternative name (e.g. server is called server01.domain.com, and website is called www.application.com).
Client-side tasks
---------------------------------------------------------------------------------
1. Client must be using IE 5.x+. If client is running IE 6, ensure that "Enable Integrated Windows Authentication (requires restart)" is selected from Tools > Internet Options > Advanced.
2. Web site MUST be recognized as Local Intranet (not Internet Zone) site to client. I have not seen any documentation explaining why, but I just have never been able to get it to work otherwise. If necessary, specifically add this to Local Intranet sites list.
3. Client account must not be marked as "Sensitive, Do not Delegate" in AD Users and Computers MMC.
If all of that does not work, then there is possibility of bad hardware killing UDP packets for Kerberos (it has happened to me before).