Previouse versions have worked on 80min/700MB CD-RWs for me.

Have you tried a full wipe? You will need to do that now and then to flatten out the dips and bumps made by several times rewriting. Yes it takes some time.

btw, k3b doesn't do a full wipe when I tell it to, on my system. I need to use cdrecord then.