Master address - not saving choice
I'm not sure this is the answer Drew is looking for or it even addresses his issue.  It sounds like it was working for him and then he had a timeout and it messed a number of them up.  The comments, which I added too many to, show that it doesn't work in some cases.

To import contact with a master address belonging to someone else, you need to include the actual address along with the address belongs to.  It is looking for the ID of master address.  How one might know that without sql is beyond me.  Whenever I've imported people with shared addresses, I've imported all the people each with an address and then wrote some sql to pull out the address id of those that would be the master and id of the contact that would use that address and id and did an import update.

I just imported a Joe Blow into Demo46 having him share an address id 3.  My cvs had first, last, street, city, state, postal, country and master address belongs to.  

I'm guessing way back when for ease of implimenting shared addresses it appears it was decided not to quite do them as relational database should.  You'd expect the id to be there and for the forms, queries, etc. to follow that id for the address, but it appears it depends on the address actually being in the record.  I suspect the contact form sees that and does a copy when you share an address or the master gets changed.

So Drew you might look at your database and see if you have records in civicrm_address that have a master address id but the street, city, etc. are blank.  If so this sql should fix it.  (A caution, I wrote this sql a while ago but it think it's still fine.  In case your wondering why it is ca and pa, I was dealing parents and children.)

update civicrm_address ca,
       civicrm_address pa
set    ca.street_address = pa.street_address,
       ca.city = pa.city,
       ca.state_province_id = pa.state_province_id,
       ca.postal_code = pa.postal_code,
       ca.postal_code_suffix = pa.postal_code_suffix,
       ca.country_id = pa.country_id
where  ca.master_id = pa.id
and    ca.master_id is not null
and    ca.street_address is null


If you don't have the master_id populated but you do have the two people both having the address, you could write some sql to add the address id of the first to be the master_id of the second.