Once the installation starts, be patient because it can take a while.
If you just double click on the .msp file from Windows Explorer, the installation will start but it will very soon rollback and you will see this error in the application log:
Log Name: Application
Date: 16.10.2012. 10:30:01
Event ID: 1024
Task Category: None
Product: Microsoft Exchange Server - Update 'Update Rollup 4-v2 for Exchange Server 2010 Service Pack 2 (KB2756485) 14.2.318.4' could not be installed. Error code 1603. Windows Installer can create logs to help troubleshoot issues with installing software packages. Use the following link for instructions on turning on logging support: http://go.microsoft.com/
You may also ran into some blog posts that say to try setting the execution policy in Powershell from RemoteSigned to Unrestricted, but that did not help in my case.
There, I hope it helps someone.