Solution:
Can you upload by FTP to that folder? It could be a problem of lack of disk space (or quota), specially if this is a shared hosting. But even in VPS or dedicated, sometimes the /tmp directory where PHP first uploads the files is mounted from a different filesystem than /var (where the apache vhost root is probably located). That could explain why you can upload it but not move it.