This issue happens mostly on the Farm installation. Everyone will say to recreate the UPS, restart the server and then it should work fine. But if you have used the Custom properties and created a managed property in Search then its very difficult to recreate it and then to create it again. The better solution so far i have researched is the following
Stop the User Profile Synchronization service
Stop the User Profile Service
Start the User Profile Service
Start the User Profile Synchronization service.
I hope the above should help you resolve the issues.