I was thinking about a secondary form... maybe that would be easiest. Especially because in the join table, I am linking the Group_ID to a Contact_ID. The Contact_ID is based on the autoincremented ID field (primary key) in the contact table.
That's not really a problem; you can insert the contact, get its newly-generated Contact_ID and use that for your next insert (into groups_contacts). One form or two is mostly a consideration of what you want (or think is better) for user experience.

Would that do? Then I'd need a way to insert each checked value into the groups_contacts join table.
That's essentially what you want, just need to add names to the checkboxes:
PHP Code:
while($row = mysql_fetch_array($result)) {
  echo '<input type="checkbox" name="group[]" value="' . $row['ID'] . '" />' . $row['Name'];
} 
Upon processing the form, that'll give you an array of the selected group ids to insert for the contact.