Try downloading this file:
Then place it in this directory, alongside the dll that is already there:
C:\Program Files (x86)\Quake 3 NEW New Filesystem\uie
Can you post a console log?
When the problem occurs, type "/condump temp.txt" in the console (without the quotes), locate the temp.txt file (likely in %appdata%\Quake3\baseq3) and post it here.
I think the general steps are as follows:
1) Download the Linux test build zip from ioquake3.org/get-it/test-builds/ and unzip it somewhere
2) Make sure you have the SDL2 package, using a command like: sudo apt-get install libsdl2-2.0-0
3) Make a directory named baseq3 alongside the test build executable, containing pak0-pak8.pk3. Pak0.pk3 is from the Quake 3 CD and the other paks can be downloaded from ioquake3.org/extras/patch-data/
I can't guarantee this is all that will be required, but it might work or at least get your started.
What is your com_maxfps setting? Try setting to 125 if it isn't already.
If this is a UIE-specific bug, I would recommend just to use the config file method of adding bots, if that is sufficient for your purposes.
The script just contains commands like you would type in the console, each command on its own line. You can see the syntax for the addbot command by typing /addbot in the console while the game is running. A .cfg file to add bots might look something like this, with the numbers being the skill level. You can use the /exec <filename> command to run it.
addbot anarki 2 red
addbot angel 2 red
addbot biker 4 blue
Have you considered using a cfg script containing addbot commands to handle adding bots, instead of using the UIE menu? If you could reproduce the problem in that configuration it would be a lot easier to debug.
I'm a bit short on ideas on this one. I haven't even been able to find a "failed to connect" message string searching the source code for both Q3 and UI Enhanced. Are you sure that was the exact message?