When long usernames are used, Samba IMO fails to map them in all situations to/from their local representation. A customer of ours reported such a problem in a Samba "as Domain client" environment ("security = domain") using a WINDOWS2003-PDC. All users with names shorter than 9 characters had no problem authenticating, but all users with names longer than 8 chars were rejected by the PDC (Samba error NT_STATUS_NO_SUCH_USER).
Since I have no PDC under my conbtrol, I tried it with "security = server", but then Samba authenticates correctly using the mapped user name (verified using tcpdump).

As a workaround, I suggested to the customer to add the username to username.map _including the domain name_, i.e., 
--snip-- username.map:
username = DOM\LONGUSERNAME
--snip--
which fixed it for him.

But perhaps the following patch would also fix the problem in Samba:
--snip--
--- samba-3.0.24.orig/source/auth/auth_util.c   2007-02-04 19:59:14.000000000 +0100
+++ samba-3.0.24/source/auth/auth_util.c        2007-02-26 11:19:55.736309000 +0100
@@ -1596,6 +1596,10 @@ struct passwd *smb_getpwnam( TALLOC_CTX 
                p++;
                fstrcpy( strip_username, p );
                fstrcpy( username, strip_username );
+#if 1 /* Think of a "username = LONGUSERNAME" mapping in the username.map (for DOM\LONGUSERNAME) */
+               /* The name as used for SAM authentication may have been mapped locally */
+               map_username(username);
+#endif
        }
 
        /* just lookup a plain username */
--snip--