I had this problem, and the solution was permissions on /media/k2/items/cache and /media/k2/items/src - even though the k2 "information" page reported them to be writable.  so my solution is to check and double check the permissions by hand...

 

the way i discovered the problem: following frm Nick's suggestion, i added

echo $handle->log;exit(log);


to the save() function in administrator/components/com_k2/models/item.php, then kept moving those two lines down through the function and re-trying the upload until i could see the problem.

hope that helps,

asdwer