Обновление: Через два дня проблема повторяется..
Обновление 2: Проблема решилась переконфигурацией рсположения USB кабелей. Похоже, что были помехи откуда-то. Но в таком случае непонятно, почему эти помехи не наблюдались при заходе в БИОС и при запуске Windows. Так что драйвер в Линуксе, скорее всего, глючный.

Проблема:
Долго (около минуты или дольше) определяется USB-клавиатура при подключении к (и при загрузке) Linux Ubuntu 12.04 (версия ядра: 3.7.5-pf). После определения клавиатура продолжает работать до следующего отключения/перезагрузки.
При этом в dmesg появляются такие сообщения:читать дальше

Решение:
В одном из файлов: /etc/modules.d/*.conf прописать такой параметр для модуля ehci_hcd 
options ehci_hcd ignore_oc=1
После выполнить: sudo update-initramfs -u -k `uname -r`
После перезагрузкит модуля, клавиатура начинает определяться за несколько секунд, как и должно быть.

Пояснения:
Клавиатура Zalman ZM-K300M, подключена через USB-hub вместе с мышью (тоже low-speed), при этом мышь работает нормально. При подключении клавиатуры напрямую (без хаба) тоже бывают пообные ошибки, но гораздо реже.
Параметр ignore_oc: ignore bogus hardware overcurrent indications (bool). Включает игнорирование ложных определений перегрузок по току. А ошибки USB устройств -110 — это вроде-как именно перегрузки по току. Перегрузок действительно никаких нет, т.к. в БИОС клавиатура работает хорошо.
Судя по результатам поиска, это ошибка в драйвере ehci_hcd, по хорошему — надо бы обновить ядро, но тогда придётся снова выбирать и настраивать лучший драйвер для видеокарты (AMD Radeon).

Ссылки:
USB errors (and hotplug work-around)
Неисправленный багрепорт на Ланчпаде