I've turned off FastCGI and it's allowing me to upload again. Whether it will work for the people that had the same issue before, who knows!
Am I losing much by having FastCGI turned off?
Would it be worth considering using nginx instead of apache?
I only have two sites - One is just a general forum, the second is where people upload large files.