У меня была аналогичная проблема с 12.04, запущенная в качестве Parallels VM, apt-get update дала med BADSIG для us.achive.ubuntu.com. Я переключился на другое зеркало (см. Ссылки в https://help.ubuntu.com/community/Repositories/CommandLine) в файле /etc/apt/sources.list и теперь обновляет работу снова.