Here are the steps I would take to troubleshoot/fix your issue:

1. Clear the SharePoint configuration cache.
http://blogs.msdn.com/b/jamesway/archive/2011/05/23/sharepoint-2010-clearing-the-configuration-cache.aspx

2. Restart the user profile sync service via the Central Admin site.

3. Considering you have two farms (one farm is consuming the UPA off another farm as per your comment, please re-check all the steps to configure cross farm UPA services.. http://social.technet.microsoft.com/Forums/en-US/sharepointadminprevious/thread/7eb602f9-fe3d-4117-a0b0-c36e27dc8df6/

and

http://www.sharepointninja.com/Blog/Lists/Posts/Post.aspx?ID=44

Ensure things like trusted farm and certificates etc are done properly.

4. Delete the UPA proxy on the consuming farm and follow the steps here. http://blog.schauweb.dk/post/2010/12/01/User-Profile-Service.aspx
You will have to recreate the UPA proxy again.

5. Check if you can successfully view the 'Timer Job Definition' page in the 'publishing farm'.

6. Refer to this thread to assist you with 'The configuration database was queried for a non-existent object'. http://social.technet.microsoft.com/forums/en-US/sharepointadminprevious/thread/acc425aa-82bb-498e-8423-8cdffbc8b251/

and

http://sharepoint.stackexchange.com/questions/33645/remove-uninstalled-feature-when-feature-guid-not-recognized