If you have a state/province field on its own, it will have all options for the countries' states you enable on your site. If you have a country field alongside a state/province field of the same location type, the state listing will depend upon the selected country (regardless of whether the country's states are enabled).
My hunch is that you have different location types for the two fields. Changing them to be the same should make it work.
(While it may seem maddening at first, it's a good feature. You can have multiple addresses in your profile, and if your home state field were to change as you set the work country field, that would be a problem if your addresses are in different countries.)
Counties work similarly with regard to states, except you must use a state field: there are so many US counties with repeating names that it would otherwise be a big problem.