I use atftp which has the multicast option as a default (although it sounds like network contention is not your problem either).I don't know, it sounds like dhcp may be working but tftpd not.
I think the 640K limit is a legacy / vagary of etherboot (http://etherboot.org/)... and most vendors don't bother with it anymore. There are some good discussions about this out there e.g. http://www.mail-archive.com/ltsp-discuss@lists.sourceforge.net/msg07883.html.Have you tried tftping to the server, to make sure you can get the file? Also, how big is the file? A lot of netbooters can't cope with anything bigger than 640K (Thanks again, Bill!). So you have to make an etherboot which works with your NIC, and load that first, then have etherboot load the kernel.
I don't know how to make the etherboot,Well, if you are lucky you can find the exact image you need at http://rom-o-matic.com/. Also, if you have the luxury of flashing your NIC PROM, there is fresh PXE code at http://downloadfinder.intel.com.
My scripts are at http://lyre.mit.edu/~kkeville/GenDHCPentries and http://lyre.mit.edu/~kkeville/makeMAC. They are a little easier to read (although not as robust) as the previously mentioned scripts.