おそらくこんな感じです。
Ubuntuが提供するパッケージは基本的にはファイルを全て内包する形で提供されていますが、配布条項上の理由で直接パッケージに収めることのできないファイルを扱う必要がある場合などのために、外部からダウンロードして補填するための仕組みというのも備わっています。（その手助けをしているのがupdate-notifier-commonです）
そのため、この処理が発生した時のパフォーマンスというのは安定感のない "ダウンロード" というものに左右されることになります。実際、ダウンロード速度がとてつもなく遅くなっていて、完了まで数十分も待たされたりすることがあります。
お二方の場合は、たまたま不安定な状態に当たってしまった、ということではないでしょうか。
ちなみに、どのパッケージがダウンロードを必要とするのかは「/usr/share/package-data-downloads/」ディレクトリーを覗くとわかります。


それから、「lock が取得できませんでした」といったエラーが出てもlockファイルは削除しないでください。
そのエラーが出るのは（基本的には）裏で同系のプログラムが走っているためで、重複した操作をさせないためにロックしています。
これも、（基本的には）少し間を置いて実行すれば通るようになります。