I ran into this at work last week, and must have talked to the same guy at Microsoft.

No point rehashing it – Jared did a great job writing it up:

http://jaredmatfess.wordpress.com/2013/02/26/sharepoint-2010-people-picker-is-having-a-hard-time-finding-people/