принцип такой, что в том объекте на который забиндена строка грида, должны быть свойства наподобие:

CompanyID (например Guid)
и
Company (сущность с атрибутами)

тогда сам comboboxcolumn можно привязать к CompanyID, а сортировку к "Company.Name"
Не помню генерятся ли в датасетах навигационные свойства (такие как в примере выше Company),
если нет то доделать их в partial классе у типизированного DataRow

можно проще, вынести в тот запрос к результату которого приделывается грид поля CompanyID (Guid) и CompanyName (string), сортировать по 2му