I have the same problem.
Is there a particular location where we must create the temp folder? Or a particular name we must give it?
I created one named zztemp on our server, and put the correct URL for that folder into the "Back up to Folder" section of the job.
That temp folder definitely IS writeable - I even changed permissions to 777 to see if that would work! But I still get the same 'temp dir not writeable message' whether the permissions are set to 755 or 777.
I'd appreciate help on this one, as it has me stumped!