Тоже было подобное, не мог установить kdelibs из-за отсутсвующего в базе данных необходимого пакета. Оказалось, что яндексовское зеркало было устаревшим. Поставил в качестве основного http://mirrors.kernel.org/archlinux и всё стало нормально. Работает даже быстрее, чем Яндекс, хотя иногда выбрасывает. Но в целом доволен.
Возможно, дело в этом: http://archlinux.org.ru/node/181?