After installing a new server, I got the upload_max_filesize message from WordPress (from php) after I tried to upload a large image file:

Of course I forgot to edit the /etc/php5/apache2/php.ini file at line 877:

; Maximum allowed size for uploaded files.
; http://php.net/upload-max-filesize
upload_max_filesize = 2M

Just 2Mb is not much… Can be altered though!