Editor does not have permission to upload files?

I can’t believe I’m posting about this…I’m sure I’m missing something really obvious.

The problem:
When I login as “Administrator” I can upload files no problem. When I login as a user with the role “Editor”, create a new post and select the “Set Featured Image” button, the following message is displayed:

You do not have permission to upload files.

What I’ve tried so far:
1. I’ve read about Roles and Capabilities in the Codex and it says that Editors should be able to Upload Files.
2. I’ve also checked in the Settings Media Screen, but there are no options to define a minimum role to upload files.
3. I’ve disabled all plugins to see if that helps, but it didn’t.

I’d love to know how to fix this…