civicrm_location_add() is hardwired to the first location. Thus it cannot be used when multiple locations per contact is desired. It creates a fixed contact array and manipulates the first location. Instead, CRM_Core_BAO_Location::getValues() needs to be used to get all of a contact's locations, merge in the new data, and save the record.
This patch almost works, however new non-primary locations with no address are for some reason created with a state and country. I couldn't figure out why.
I ended up abandoning trying to do my importing with the location API since even if I could get this fixed, the server was being overloaded with the overhead of looking up all locations everytime I wanted to add a new location for a contact (and this import adds 3-4 locations per contact * 30k contacts).
But this is a start to get the location API to a usable state.