SELinux restricting my system app even while it was signed with the same key as the previously shipped one!
Well I found out that I messed up. I was building it with the wrong manifest. It should had been android:sharedUserId="android.uid.system" instead of android:sharedUserId="android.uid.systemui". When I compared the manifests (thank you apktool for decrypting the manifest for me!) it become obvious. Replacing the related bits in the manifest fixed it. Problem solved. Probably I was just using the wrong repository.