Can't upload to the media library

We keep getting this warning whenever we try to upload a new image to the media library.

“filenamehere.jpg” has failed to upload due to an error
Unable to create directory uploads/2013/11. Is its parent directory writable by the server?

We are running the newest version of WP and all plugins are up to date.

I can upload files via FTP, but my end user clients do not have nor want to use FTP. They want and need the convenient CMS.