For the record, I finally figured out what the problem was. (!!!)

In /etc/services on the problematic clients, I had all of my custom ports 
listed, as well as the default ports (10080, etc). 

I had the default ports (10080 TCP/UP) at the very bottom, below all of my 
custom ports. I moved the default ports above my custom ports (and restarted 
xinetd) and it started working.

The default ports were above the custom ports on the other clients that were 
working, because I left them in place, and didn't move them down to where all 
of my custom ports were listed at the bottom. Didn't notice until today... 

Rejoicing,
Jeremy