When I got my Iphone 4 I transfered my apps of which I had bought in Rock and of course when Rock transfered to my new phone they unauthorized the apps on my 3gs.
After I got my Iphone 4 fixed the way I wanted I turned my attention back to my 3gs.
I tried to remove the apps that I had transfered to my Iphone 4 and could not.
I emailed Rock support and they said the only way I could remove them was to restore the phone.
What I think is that Rock and or Cydia has done something about storing the licenes for paid apps and you cannot remove a paid apps unless a valid licenes is present.
This really sucks because you cannot remove the apps or download new apps.