Thanks user "mukky" for helping me troubleshoot today.
He has a tragic server, and I think many of them may be having this problem.
Starting a lobby is sticking on "validating." The reason for this is that his server was not providing tf2c a list of maps through rcon. I logged in to the server console, and this is what I saw when I did the "maps *" command myself.
] rcon maps *
autokick is disabled for TF2C | ninjaMooCow
-------------
PENDING: (fs) arena_badlands
PENDING: (fs) arena_byre
PENDING: (fs) arena_granary
PENDING: (fs) arena_lumberyard
PENDING: (fs) arena_nucleus
PENDING: (fs) arena_offblast_final
[......]
There is an article that talks about this "bug" here: http://forums.srcds.com/viewtopic/5244
It suggests making a mapcycle.txt with every map listed in it twice. Apparently, that works.
I also suggested that the server owner open a ticket to tragic with the above information, as it appears as if the server configuration is not working correctly.