I had this reported by a user today and wasn't able to debug it at all, until I searched for the error message in the OpenSSH sources and found in ssh.c:

        /* Get user data. */
        pw = getpwuid(original_real_uid);
        if (!pw) {
                logit("You don't exist, go away!");
                exit(255);
        }

From the user and support perspective, this message ("go away", implying that there is a "here" and a "there", which is where the server kindly requests the user to stay) suggests that there was an issue with the target SSH server. Having seen the ssh.c source, it was in fact simple to verify that the user tried to log in during a 30 second unavailability of the LDAP server that serves her own UID. 

Considering the fact that this is only visible to the user, it would be prudent to disclose the actual condition. "ssh: Error resolving your UID" would have been helpful already.

The same message can be found in ssh-keygen, by the way. Thanks for your time! :-)