Acabei seguindo este guia que explica que openbsd-inetd deve ser instalado também e eu também tive que definir RUN_DAEMON="yes" no meu arquivo de configuração tftp em /etc/default/tftpd-hpa .
UPDATE # 1
O link acima não funcionou mais, então encontrei uma alternativa aqui, intitulada: Rodando o TFTP Server no Ubuntu 12.04 LTS (Preciso) UPDATE .