Yes, you need to allow the Tableau server to see the external map server. Or in our case, give the Tableau Server the ability to see the internet. You can obviously test this on the server itself by opening a web browser. You may need to change the proxy settings in Internet Setting on the server to get this to work. Your IT department may have to do this for you as it may be set by Group Policy.
You don't mention whether it worked with previous 8.1.x builds. 8.1 replaced the Tableau networking stack and we are still finding some proxy configurations that don't work. Please contact support to work with them and create a network trace.
The problem has been solved in Tableau 8.1.4.