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.