Я могу ошибаться, но я думаю, что первый аргумент функции check_box_tag - это фактическое имя ввода, поэтому вместо
check_box_tag :company_ids, company.id, @user.companies.include?(company), :name => 'user[company_ids]'
Вы можете попробовать что-то вроде
check_box_tag 'user[company_ids]', company.id, @user.company_ids.include?(company.id)
Дайте мне знать, если это работает!