The uploaded file exceeds the upload_max_filesize directive in php.ini.

By increasing upload_max_filesize in your php.ini.

You might have different versions of php.ini files in your installation. To check which one you should be altering its upload_max_filesize line, use:

php -i | grep "Loaded Configuration File"

Then do a

sudo service nginx restart

I bumped into exactly the same problem few days ago. The solution I found was adding the following lines to php.ini in the root directory of the Wordpress install.

post_max_size = 16M
upload_max_filesize = 16M
memory_limit = 128M

However, the system didn’t seem to honor the settings. Instead, editing /etc/php5/fpm/php.ini solved this problem for me.