User id's with values greater than 65536 ( or is it 65535? ) don't work. For instance, I can create a user with uid 100,000. That user can't log in. Watching syslog during the login shows a session open for the user, then immediately close. 'su' spits at the username with a invalid arguement error and refuses to set the userid to 100,000. This has become an issue at NCSU where the eos/unity system now has ~70,000 users.
The kernel's UID type is only 16 bits. Sorry. When this is fixed in the kernel, it will work elsewhere. You might try experimental 32-bit uid support, available at: http://www.engin.umich.edu/caen/systems/Linux/highuids