Problems with Search Builder: Trying to find records with empty Country field
Try changing the search condition of the Search Builder 
ignore is_primary flag 

look for:
contact -> country -> home -> is not null (also change the address type)
contact -> contact type = Individual 

by this way you can select all the record with country field null also you can use batch update