Recently I ran into an issue with the default s3cmd package (v1.0.0) in the Ubuntu repositories. When using a very specific IAM user with PutObject only allowed for a bucket, files over 15MB would error out. After digging into the issue, I found out this was due to the way s3cmd (or maybe just s3 in general) handles large file uploads. Anything over 15MB will be broken into smaller pieces of a multi-part upload.
I am still unaware as to why the PutObject permissions were insufficient on v1.0.0, however if you upgrade to the latest, currently 1.5.0, it handles multi-part uploads much better. Here are the commands needed to get updated.
Update: The previous method will only work for Ubuntu 14.04, here is a better method that will work across distributions and versions.
First ensure that pip is installed. On Ubuntu run
sudo apt-get install python-pip
Then install s3cmd
sudo pip install s3cmd==1.5.0-alpha3