User Profile doesn't have any connection to the People Picker.
What I'd recommend is that if you're not seeing all of the results you expect and the users you expect to see are in an enabled state within AD and the Web Application pool account has read access to the OU the users reside in (let us know if this is a multi-domain scenario), take verbose logs and repeat the scenario. In those logs you should find the LDAP call (search for 'LDAP' or 'GC://') and it will tell you the number of returned results. Does that value differ from what you see in the People Picker?
Also note the People Picker caches values in the browser cache -- using an InPrivate mode to test is always a good idea. It also retrieves results from the sites User Information List, so you may find some objects which have been deleted/disabled from Active Directory.