Tema de existencia de archivos y permisos son las únicas 2 opciones que me quedan.
Mirando move_uploaded_file vemos esto en lo devuelto:
Cita: Devuelve TRUE en caso de éxito.
Si filename no es un archivo válido subido, no sucederá ninguna acción, y move_uploaded_file() devolverá FALSE.
Si filename es un archivo subido válido, pero no puede ser movido por algunas razones, no sucederá ninguna acción, y move_uploaded_file() devolverá FALSE. Adicionalmente, se emitirá un aviso.
Entonces tenemos que probar esos casos.
http://www.php.net/manual/es/function.is-uploaded-file.php
Con esto descartamos el 2do caso.