I'm getting OutOfMemoryError error when removing apps. How to resolve this?

I cannot update or remove any app because android reboots every time I try to do so. I've checked the problem using adb logcat *:E and I've found this:

E/dalvikvm(20261): adjustAdaptiveCoef max=4194304, min=1048576, ut=619
E/dalvikvm-heap(20261): Out of memory on a 21982984-byte allocation.
E/AndroidRuntime(20261): !@*** FATAL EXCEPTION IN SYSTEM PROCESS: PackageManager

E/AndroidRuntime(20261): java.lang.OutOfMemoryError
E/AndroidRuntime(20261): at java.io.ByteArrayOutputStream.toByteArray(ByteArrayOutputStream.java:122)

Please note that my phone is rooted. And I'm using Link2Sd too, and I've tried to clear the dalvik-cache but that didn't make an improvement in the situation.