Never mind, I'm from Belgium and Tableau thought the states and counties were in Belgium.
After changing them to United States, it was correct.
Apparently Tableau is a very US centric company...
Yes, I had this trouble as well. For anyone else located internationally, it can be fixed by clicking in the menu Map>Edit Locations and then selecting the correct country corresponding to the data (United States) in the dropdown menu.