I also tried and tried to get the service to work with no luck, none of the posted suggestions worked for me. So I decided to see if I could do this another way. I ran across Yahoo's PlaceFinder, it is implemented a little different in that it is a REST web service. More info can be found here:

Yahoo! PlaceFinder Guide

I should point out I am an Absolute Beginner, thus why I am watching this series, so if there is a better way todo this I would love the insight. Here is the code I came up with:

private void myButton_Click(object sender, RoutedEventArgs e)
            GeoCoordinateWatcher myWatcher = new GeoCoordinateWatcher();

            var myPosition = myWatcher.Position;

            string latitude = "47.674";
            string longitude = "-122.12";

            if (!myPosition.Location.IsUnknown)
                latitude = myPosition.Location.Latitude.ToString();
                longitude = myPosition.Location.Latitude.ToString();

                Uri uri = new Uri("http://where.yahooapis.com/geocode?&gflags=R&location=" + latitude + "+" + longitude);

                WebClient wc = new WebClient();
                wc.DownloadStringCompleted += OnDownloadStringCompleted;

        private void OnDownloadStringCompleted(object sender, DownloadStringCompletedEventArgs args)
            if (args.Error == null)
                XDocument xdoc = XDocument.Parse(args.Result);
                //Get the City
                myTextBlock.Text = xdoc.Element("ResultSet").Element("Result").Element("city").Value.ToString();
                //Get the State
                //myTextBlock.Text = xdoc.Element("ResultSet").Element("Result").Element("state").Value.ToString();
                //Get the City, State, Zip
                //myTextBlock.Text = xdoc.Element("ResultSet").Element("Result").Element("line2").Value.ToString();
                //Get the Country
                //myTextBlock.Text = xdoc.Element("ResultSet").Element("Result").Element("country").Value.ToString();

You will need to add a reference to your project for System.Xml.Linq so that you can parse the XML data that is returned from Yahoo. And if you plan on using this as a solution you will need to get a developer ID from Yahoo to use it, refer to the link above about this.

I do like the flexibility of the XML returned and that I can grab just the city or state. Hopefully this will help someone else out struggling with the Microsoft Service. 

****NOTE**** the code block seems to be messing up my Uri address. It should be:

Uri uri = new Uri("http://where.yahooapis.com/geocode?&gflags=R&location=" + latitude + "+" + longitude);