Hi,
This would indicate that something ins missing in your customers address. For example, if you had removed/disabled the country field for them and later on added it and added shipping method restrictions on the zones, such issue could happen for the users who registered before the change.
I would recommend to look at the address entry in the hikashop_address table of your database before and after saving it in order to see what's different. Then, a simple query should be able to fix the problem for all the customers with the problem.