I was able to solve this very same issue.
When booted into safe mode. Run an elevated CMD prompt and run the following.
REG ADD "HKLM\SYSTEM\CurrentControlSet\Control\SafeBoot\Minimal\MSIServer" /VE /T REG_SZ /F /D "Service"
REG ADD "HKLM\SYSTEM\CurrentControlSet\Control\SafeBoot\Network\MSIServer" /VE /T REG_SZ /F /D "Service"
net start msiserver
Then you must from the start menu find the "Kaspersky Modify/Uninstall" shortcut in the Kaspersky menu object. If you try to uninstall from the add/remove programs (appwiz.cpl) it gives you a warning.
It successfully uninstalled and I rebooted back to normal. Obviously Kaspersky isn't installed anymore, but having a booted server is better than not.