3110762 - UME is not working after upgrade - NoSuchMethodError - InternalUMFactory.loggedInUserHasPermission

After upgrade to NW 7.5 SP18 or higher, the User Management Engine (UME) is not working. It gives an error "You are not authorized to access this application; contact your system administrator" in every operation (search, insert, etc).

In addition, the following error is logged in the defaultTrace files:

[...]
[EXCEPTION]
com.sap.security.core.wd.exception.UmeUiException:
at com.sap.security.core.wd.umeuifactory.UmeUiFactoryCompInterface.handleThrowable(UmeUiFactoryCompInterface.java:3190)
at com.sap.security.core.wd.umeuifactory.UmeUiFactoryCompInterface.hasPermission(UmeUiFactoryCompInterface.java:1653)
at com.sap.security.core.wd.umeuifactory.wdp.InternalUmeUiFactoryCompInterface.hasPermission(InternalUmeUiFactoryCompInterface.java:601)
at com.sap.security.core.wd.umeuifactory.UmeUiFactoryCompInterface.hasSimplePermission(UmeUiFactoryCompInterface.java:1862)
at com.sap.security.core.wd.umeuifactory.wdp.InternalUmeUiFactoryCompInterface.wdInvokeMethod(InternalUmeUiFactoryCompInterface.java:1079)
at com.sap.tc.webdynpro.progmodel.generation.ExternalControllerPI$ExternalInterfaceInvocationHandler.invoke(ExternalControllerPI.java:339)
at com.sun.proxy.$Proxy669.hasSimplePermission(Unknown Source)
at com.sap.security.core.tools.HomeView.wdDoModifyView(HomeView.java:246)
at com.sap.security.core.tools.wdp.InternalHomeView.wdDoModifyView(InternalHomeView.java:292)
Caused by: java.lang.NoSuchMethodError: com.sap.security.core.InternalUMFactory.loggedInUserHasPermission(Ljava/security/Permission;Z)
[...]

SAP NetWeaver Application Server Java 7.5 SP18 or higher

user management, ume, authorization, roles, role, user, users , KBA , BC-JAS-SEC-UME , User Management Engine , Problem