You sure the directory is 777? If the files could not be moved I would think not.
Anyway I would recheck permissions and try a thumb rebuild for missing thumbs once again.
Try localizing it just to 500
If the permissions persist have you tried switching image processors as well?