In order for me to get this to work, I had to modify the original patch to have the following:
$addr_params['contact_id'] = $contactID;
$addr_params['address']['contact_id'] = $contactID;
But, now it works flawlessly for me. I'm using CiviCRM 3.1.5 and Ubercart 2.2 in Drupal 6. Anyone else have to do something like this, or do I just have something weird going on?