Michel, I don't have this setup, so this may not be of much help, but that's a Kerberos issue.  There is a .pdf that EMC has to troubleshoot Kerb issues (docu69146.pdf) and I found it helpful to find some minor issues with what I thought was a Kerberos issue.  If you haven't used it already, it's worth a try to get the more obvious problems squared away.

I'm not entirely certain on your setup (never having run Samba AD here) but does the Samba server sort of act like a proxy to your main AD environment?  If so, you may be running into a double-hop issue.  Years ago I had this issue when I was trying to get a scale-out SQL Reporting environment set up (IIS web server, SQL server, SQL reporting server) and I had to call Microsoft to get assistance.  At the time there was little information I could find that discussed this setup, and it took the engineer a few days, but he was able to come back exactly with the solution I needed and I was able to get it working.  A few months later, a KB article showed up describing how to accomplish this sort of scale-out environment (I've always thought I was the reason for that KB article!).

So maybe completely unrelated, but I think it's worth making sure your Kerberos setup is correct (all SPN's exists, etc.) first.  Then perhaps some time researching the double-hop issue to see if it gels with what you are seeing.  Hopefully I'm not sending you on a wild goose chase.