When installing tftpd-hpa, as a security measure, the service does not allow uploading new files. It does allow overwriting existing files, provided that the permissions are set correctly (as expected). The idea behind this is to secure TFTP a bit by only allowing uploads if the file already exists (and is writable). But this can be very tedious in some cases, where a lot of files have to be uploaded, and it is not possible to guess the names to create them in advance.
It is possible to configure tftpd-hpa to allow the creation of new files by adding the -c or --create parameter when starting the daemon.
For Ubuntu and Debian, this means editing the file /etc/default/tftpd-hpa, and adding this to the TFTP_OPTIONS parameter in the file:
After the edit, restart tftpd-hpa:
sudo /etc/init.d/tftpd-hpa restart
Also, don't forget to make the user running tftpd-hpa (normally: tftp) the owner of the tftp directory:
sudo chown -R tftp /var/lib/tftpboot