>For some reason I can't come up with the correct generic term for State/Province that would apply for all countries.
>
>Region?

Region isn't it, even in the U.S. It implies a larger area like the midwest or northeast. State/Province is as close as you are going to get.