I think it is a software bug, I tried syncing with the contacts on my Mac, I also tried syncing with my Outlook on Windows and had the same issue. I manually edited an address on my iPod Touch and even though it displayed "United States" as the country in the veiw mode, in the edit mode it said to choose a country, I selected "United States" in the drop down, and it worked with the maps program.
When I synced it again with my contacts programs it did not change any fields. For those of us who have 100+ contacts and don't want to go through edit each one on the iPod Touch and set the country, it should automatically sync with the contacts on my Mac or Outlook on my PC.