Okay. Your configurations are the default configs (with the notable
exception of enabling the xinetd.d/tftp service).

On my x86_64 laptop running Fedora 16, with iptables reasonably normal,
I installed "tftp" and "tftp-server", and changed "disable = yes" to
"disable = no" in /etc/xinetd.d/tftp. Then, I ran:

 service xinetd restart

Next, I put a dummy file in /var/lib/tftpboot:

echo "Hello, Fedora." > /var/lib/tftpboot/hello.txt

Then, I tested a tftp connection across the loopback:

[spot@pterodactyl ~]$ tftp -v localhost
Connected to pterodactyl (127.0.0.1), port 69
tftp> get hello.txt
getting from pterodactyl:hello.txt to hello.txt [netascii]
Received 16 bytes in 0.0 seconds [44990 bit/s]
tftp> quit
[spot@pterodactyl ~]$ cat hello.txt
Hello, Fedora.

Okay, that works. I'd be a bit worried if it didn't. :)

Next, I tried to connect from a F-14 x86_64 machine on the same network
(actually connected to the same switch too), and that worked fine:

[spot@treefrog ~]$ tftp -v pterodactyl
Connected to pterodactyl (XX.XX.XX.XX), port 69
tftp> get hello.txt
getting from pterodactyl:hello.txt to hello.txt [netascii]
Received 16 bytes in 0.0 seconds [18910 bit/s]
tftp>

Now, I did notice a failure when I was trying to connect to the server
from a VM on that separate machine. From the server logs:

Oct 12 14:10:22 pterodactyl in.tftpd[8609]: tftpd: read(ack): Connection
refused

The client would connect, but it would not download any files.

[spot@f15 ~]$ tftp -v pterodactyl
Connected to pterodactyl (XX.XX.XX.XX), port 69
tftp> get hello.txt
getting from pterodactyl:hello.txt to hello.txt [netascii]
Transfer timed out.

The trick to getting the VM working was to run this command on the
hypervisor level on the system where the VM was running:

 modprobe nf_nat_tftp

And within the VM itself, run:

 modprobe nf_conntrack_tftp

(You could also do modprobe nf_nat_tftp here too, because that will also
load nf_conntrack_tftp as a dependency, but I don't think you need
nf_nat_tftp on this end. Not harmful though, just unnecessary.)

Once that was done, it connected to my laptop without an issue. This
makes sense, because KVM is using NAT to handle networking inside VMs.

I did have issues tftp'ing between two VMs on the same system, but I
don't really think that is a very sensible setup, so I didn't pursue it
any farther.

Just for another data point, I setup a tftp server on my F14 system and
connected from my F16 laptop as a client, and it worked fine.

You might be able to get useful debugging by turning off xinetd and
manually launching in.tftpd in a console:

sudo /usr/sbin/in.tftpd -L -v -v -v -s /var/lib/tftpboot

Then, in another console on the server, tail -f /var/log/messages and
try to connect from the remote client. You might see errors like:

in.tftpd[8638]: tftpd: read(ack): No route to host

or

in.tftpd[8613]: tftpd: read(ack): Connection refused

Those usually imply a networking issue between the client and server.
Having more information about how the client and server are networked
together would be useful, especially if NAT is in play.

Hope that helps,