Does the server have external internet access?  Tableau uses an online map service to retrieve the maps. 

If there is no internet access, you could  try using offline maps (select "Map" from the Menu, Background Maps --> Offline) and then republishing.