One of the annoyances of teh interwebs (mostly stackexchange, actually, but not in this case) is when the wrong answer comes top of the google rankings for a common question.
So here's my contribution to making WordPress Forums for Unable to create directory - Is its parent directory writable by the server? the top google hit for this problem.
The problem, for me and many others, is not directory permissions but the path-to-uploads setting. Fix it by logging in with your admin account, and correct the path in:
Settings -> Media -> Uploading Files : Store uploads in this folder
Why was it incorrect in the first place? Because I had changed hosting provider.