kmk,
Да все дело оказалось в провайдере. Там трафик идет через прокси сервер, и как мне сказали он может "резать" заголовки пакетов.
Пока проблему решил не очень красиво:
Установил менеджер пакетов Synaptic и обновляю/устанавливаю пакеты через него, но небольшими порциями по 5-15 штук - тогда ошибок практически не возникает, за редким исключением. Если же обновлять большее количество пакетов обязательно возникают ошибки типа "Size mismatch".
Nikki1993 и kmk спасибо за ответы!