Exchange 2010 SP3 upgrade fails during preparation

I'm trying to upgrade our Exchange 2010 SP1 server to SP3 in preparation of installing a new Exchange 2013 server to take over, which requires SP3 on the 2010 machine to be able to migrate. While all prerequisite checks succeed (1 warning related to an update for failover clustering not being installed, which I'm not using anyway) I then get the following error right away 10 seconds after starting the upgrade:

The relevant part of the setup log seems to be (complete failing log here):

[12-06-2013 01:30:12.0483] [2] Creating templates
[12-06-2013 01:30:12.0483] [2] Entering CAtomOrgCtChildren::ScUpdateTemplates
[12-06-2013 01:30:12.0483] [2] Attempt to get an exclusive access to the directory
[12-06-2013 01:30:12.0483] [2] Checking if the user has enough persmissions to update templates.
[12-06-2013 01:30:12.0483] [2] Entering ScHavePermissionToCreateDSObject
[12-06-2013 01:30:12.0483] [2]  Status code check (f:\14.03.0123\sources\dev\admin\src\libs\ds\x_dob.cxx:3370)
           Error code 0X8000500D (20493): This property can't be found in the cache.
[12-06-2013 01:30:12.0483] [2] Leaving ScHavePermissionToCreateDSObject
[12-06-2013 01:30:12.0483] [2] User has enough permissions to update templates.
[12-06-2013 01:30:15.0806] [2]  Status code check (f:\14.03.0123\sources\dev\admin\src\libs\ds\x_dob.cxx:1200)
           Error code 0X80072020 (8224): An operations error occurred.
[12-06-2013 01:30:15.0806] [2]  CAtomOrgCtChildren::ScUpdateTemplates - failed to get a list of templates (f:\14.03.0123\sources\dev\admin\src\udog\exsetdata\components\server\a_orgctchildren.cxx:1205)
           Error code 0X80072020 (8224): An operations error occurred.
[12-06-2013 01:30:15.0806] [2]  CAtomOrgCtChildren::ScUpdateTemplates (f:\14.03.0123\sources\dev\admin\src\udog\exsetdata\components\server\a_orgctchildren.cxx:1336)
           Error code 0X80072020 (8224): An operations error occurred.
[12-06-2013 01:30:15.0806] [2] Leaving CAtomOrgCtChildren::ScUpdateTemplates
[12-06-2013 01:30:15.0806] [2]  CAtomOrgCtChildren::ScAddDSObjects (f:\14.03.0123\sources\dev\admin\src\udog\exsetdata\components\server\a_orgctchildren.cxx:215)
           Error code 0X80072020 (8224): An operations error occurred.
[12-06-2013 01:30:15.0806] [2] Leaving CAtomOrgCtChildren::ScAddDSObjects
[12-06-2013 01:30:15.0806] [2]  CBaseAtom::ScRefreshDSObjects (f:\14.03.0123\sources\dev\admin\src\udog\setupbase\basecomp\baseatom.cxx:1478)
           Error code 0X80072020 (8224): An operations error occurred.
[12-06-2013 01:30:15.0806] [2] mode = 'Reinstall' (61955) CBaseAtom::ScSetup (f:\14.03.0123\sources\dev\admin\src\udog\setupbase\basecomp\baseatom.cxx:537)
           Error code 0X80072020 (8224): An operations error occurred.
[12-06-2013 01:30:15.0806] [2]  ScSetupAtom (f:\14.03.0123\sources\dev\admin\src\udog\exsetdata\exsetds.cxx:882)
           Error code 0X80072020 (8224): An operations error occurred.
[12-06-2013 01:30:15.0806] [2] Leaving ScSetupAtom
[12-06-2013 01:30:15.0822] [2] [ERROR] An error occurred with error code '2147950624' and message 'An operations error occurred.'.
[12-06-2013 01:30:16.0259] [1] The following 1 error(s) occurred during task execution:
[12-06-2013 01:30:16.0259] [1] 0.  ErrorRecord: An error occurred with error code '2147950624' and message 'An operations error occurred.'.
[12-06-2013 01:30:16.0259] [1] 0.  ErrorRecord: Microsoft.Exchange.Management.Deployment.ExsetdataException: An error occurred with error code '2147950624' and message 'An operations error occurred.'.

I'm completely stuck on what is actually failing now, and why. There were domain controllers cleanly removed from the network recently, but they were never relevant – all FSMO roles and GC remained on the srv-003 server and the other ones were cleanly demoted.

Anyone have any idea what could be causing this issue?