Ok. El problema tal y como lo planteas puede apuntar a varias posibles causas:
-Permisos (lo descartamos porque veo que ya los has cambiado, tanto en los directorios como en los scripts).
-Problemas con el fichero (como me imagino que habrás probado con varias imágenes, también lo descartamos).
-Configuración del php.ini (los descartamos, pero de todas formas echa un vistazo a la directiva "upload_tmp_dir").
-Error en el formulario de envío (se podría descartar porque hace unos días te funcionaba, pero si quieres pega el código aquí y lo miramos).
Si hace unos días te funcionaba todo perfectamente y no has tocado nada, la verdad es que es raro que de pronto te deje de funcionar. Yo probaría a utilizar algun otro script para subir ficheros (para asegurarme de si es cosa del código o de la configuración).
Ya nos comentarás...
Suerte.