I have to agree. UDP packets are not guaranteed to arrive in order or even at all. UDP messages fail in exactly the overloaded environment we're dealing with here. I think it's clear that the issue at hand is not raw throughput (UDP's forte) but rather reliability (TCP's forte).
I think UDP makes sense for broadcasting time-sensitive game data, but its a mistake to use it for critical tasks like establishing the initial game connections.
Just my 2 cents.