Could not create directory error

I am running 3.1.2 wpmu with several site and I have been using the same host for many years.

I have never had an issue until recently when I keep getting an error when I try to automatically upgrade a plugin(or wordpress). It give me this error on all my site, here is an example of the error "Could not create directory. /home/directto/public_html/wp-content/upgrade/1-flash-gallery.tmp/1-flash-gallery". On various formus, they suggest checking file permission- done- they are OK, also they suggest that the issue is caused by hosters who use Fantastico to install Wordpress as well as using Pure FTP (on their end). My host uses both of these but refused to change the FTP they use (this has been proven to solve this issue),

I have a few options: 1. Change host (not really interested in this one)- I have several sites running off one install, many sites are live, so this sounds like a nightmare scenario.
2. Ask if anyone know of a patch to work around this error or any other solutions that anyone knows about.

It is bizarre that the site ran for so long without issue and nothing I do seems to fix it!

This error is very frustrating! Any help, PhP patch would be appreciated.