scossu

Turned out it was a Nginx problem:

http://stackoverflow.com/a/23764479/1069841

Also worth noting that there is a network-wide setting for max upload size in a multisite installation.