I determined that it was my firewall that was blocking the connection.
FYI, the following outgoing UDP ports should be unblocked to play OpenArena:
27950 -- Master server
27960 - 27981 -- Most OpenArena servers
10000 - 10040 -- Another small cluster of servers
27999, 15224, 21000, 62505 -- Other servers not on the standard ports
P.S. I would like to have seen something like this documented on the OpenArena FAQ.
Its nothing to do with OpenArena? was this information documented in Quake 3 Arena?