Please evaluate this code in Mathematica:
ToFileName[{$UserBaseDirectory, "Paclets", "Repository"}]
This will print to the screen the location of the paclets repository. This is the file on your computer which saves cached information from all of the functions like CityData, WeatherData, FinancialData, etc. Maybe there is something wrong with the cache here. You can delete this folder or the subfolders that are for CountryData and it will force Mathematica to try pulling the information off the web again.
Just to be sure, please try running the examples for CountryData in the documentation. Do these work for you?