IBM Support had us reconfigure our TURN server to use TCP instead of UDP. This resolved the issue for us and now calls connect in a very respectable 2-5 seconds.
1) Change the setting from UDP to TCP in the STSC mentioned here: http://www-10.lotus.com/ldd/stwiki.nsf/dx/Configuring_the_Media_Manager_to_use_the_TURN_Server_st852ifr1
2) Edit the TurnServer.properties file to comment out UDP and uncomment the TCP line.
3) Ensure all your network settings (firewall, natting, etc) allow those ports for TCP.
4) Restart the Media Manager and TURN servers.