Server is Debian so you should have ssh/shell access. Your server is *not* in a shared hosting environment, is it?
Login to the moodle and run the server phpinfo link. In that display, check the line that shows what php.ini is being loaded. For the sake of explanation am going to provide (as example) that shows php.ini being loaded is in /etc/ ... so the path to the php.ini file is /etc/
Login via ssh and make sure you are root user ... might have to sudo -s to be root.
Then, as root user, issue the following commands:
fgrep 'upload_max' /etc/php.ini
That should find a line in php.ini like this:
What is the value there?
fgrep 'post_max' /etc/php.ini
Does the value for upload_max_filesize and post_max_size match?
'spirit of sharing', Ken