По-латыни Rutilus - изжелта-красный, золотисто-красный; ярко-красный; русый или рыжий; отливающий золотом. Т.е., когномен явно смысловой, скорее всего, связанный с цветом волос.
Кажется, первый известный носитель - Спурий Навтий Рутил,консул 488; когномен также встречается в родах Марциев, Корнелиев, Семпрониев, Вергиниев.
Первый носитель когномена Рутилий - Спурий Рутилий Красс, консулярный трибун 417. Но он сомнителен, возможно, на самом деле он был Ветурием. Исключая его, первым будет Публий Рутилий, народный трибун 169 г.
Думаю, что когномен первичен.
Впрочем, полная информация из RE мне сейчас недоступна, проверю завтра вечером или в понедельник.