For me, it was all about killing and rebuilding a bigger cache. Sorry if someone is bothered by this show-and-tell, but I want it registered on SE so other people having the same problem can find an answer googling for it.
I won't select my own answer as the approved one. If someone has an answer to the issue that does not require root, that will be THE ONE.
The problem seems to be with the size of the partition the cache is in. It is mounted on a 20-30MB partition in the phone internal SD card.
The fix that worked to me was described in this blog post.
THE BLOCK BELOW IS TAKEN FROM Jimmy Halim's blog post, and is his property.
I sent him a message asking for permission, if he asks me to take this down, I will.
After browsing around, I found out that the cache folder (that I assume used by the market) is using small partition (around 20mb in my case).
So to solve this we need to change it to bigger partition.
You gonna need Android Terminal Simulator or equivalent terminal app. This will also require your Android rooted.
Type ’su’ (root permission request will be showned, you need to approve it).
Type ‘cd /’
Type ‘umount /cache’
Type ‘mount -o rw,remount -t rootfs rootfs /’ (to set the folder access to rw – read write)
Type ‘rmdir /cache’ (delete cache folder)
I personally using root explorer to do point 5-6
Type ‘mkdir /sdcard/cache’
Type ‘ln -s /sdcard/cache /cache’ (to link cache folder to /sdcard/cache – which shoud have bigger partition size)
My p1000 was rooted and had terminal emulator and busybox installed. I just typed the commands in the order described by Jimmy Halim (kudos to him).
Searching for the background to this question, I also found this forum post (in portuguese) that seems to (untested by me) solve the problem using an app.
[begin portuguese posting]
Para solucionar o problema, eu precisei modificar o tamanho do cache do telefone
[end portuguese posting]