I just wanted to post that user Nick Texidor solved this issue for anyone else having this problem. Solution is below;
For those people having problems with the uploading of files, and have already ruled out a problem with permissions, I have a solution....
The quick fix is to edit /administrator/components/com_k2/lib/class.upload.php. Go to the init() function, and change the following variables from true to false:
$this->mime_fileinfo = false; // MIME detection with Fileinfo PECL extension
$this->mime_file = false; // MIME detection with UNIX file() command
$this->mime_magic = false; // MIME detection with mime_magic (mime_content_type())
You are 'SUPPOSED' to be able to override these settings in the calling script, however, because of a fundamental flaw in the design, it doesn't actually work :^)