I don't know how I didn't run into this before, but I finally stumbled on a program that just made my life a ton better.
We run OpenLDAP for network authentication, among other things. Periodically, the Name Service Caching Daemon (NSCD) will introduce a bug that causes accounts stored in LDAP to not work properly. In the most recent iteration of Ubuntu Precise 12.04.2, the bug is that "getent passwd" will list all your users, but trying to su to them will tell you they don't exist.
All your problems can be fixed by simply installing "unscd" instead of "nscd". "unscd" or "Micro Name Service Caching Daemon" (the U stands for the micro symbol) is a direct replacement for nscd that doesn't appear to have the problems of nscd.
So if you're running LDAP on your network, or heck even if you aren't, simply install unscd. When you do, it should automatically remove nscd as you can't run them both at the same time.

I've recently started migrating much of our network services to OpenLDAP for the backend storage. I've switched completely from NIS authentication to LDAP, and even configured a Samba domain control for the few Windows logins that remain on our network.