There seems to be an issue with Wordpress 2.5 and greater regarding the inability of Contributors to upload media to their posts. When someone with Contributor permissions tries to upload, say, an image, they are greeted with the following message:
You do not have permission to upload files.
Well, I am not sure if this is a bug; it might be a design decision. Either way, versions of Wordpress prior to 2.5 do allow Contributors to upload media to their posts, so people who upgrade from pre 2.5 to post 2.5 might be affected by this difference.
A neat way to get around this issue is by installing the Role Manager plugin, activating it and granting contributors the right to upload files.