こんにちは。まずは現象の再現を試みてみたのですが、

”システム設定で最適なダウンロード元のサーバーを見つけようとしても「インターネット接続を確認してください」と出てきてしまいます。”
これが確かに出る場合はあったのですが、
・LANケーブルが外れていた
・当方Win8上の仮想16.04起動なので、Window側がサスペンドしたあとは仮想１６．０４のインターネット接続ができなくなる
の２種類の状況でしか再現できず、そのどちらも、ブラウザからのインターネット接続もできない状態でした。

お役に立てるかわかりませんが、まだ解決してないようでしたら、以下を打って結果を教えて頂けるとありがたいです。
・ifconfgコマンドの結果
・pingコマンドをダウンロード元サーバに実施した結果（ ping ftp.tsukuba.wide.ad.jp）
また、ブラウザを立ち上げインターネットに接続はできたとのことですが、そのサイトのアドレスも教えてください。

以上、よろしくお願いいたいします。

luna_lindo様

まずは、問題解消できて本当によかったです。
本件は大きく２つ問題があり、
(１番目）、ソフトウエアのアップデートもインストールもできない
(２番目）、 ダウンロード元サーバを検索しても「インターネット接続を確認してください」となる
自分はすみません、２番目の問題に気を取られていたのですが、
１番目の問題が解決できたようで、良かったです。
（/var/lib/dpkg/lockでアップデートできないのは再現可能で、
　例えばターミナルAで$ sudo apt-get install kubuntu-desktopと打ち、[Y/n]入力で止めた状態で
　ターミナルBで$ sudo apt-get install xubuntu-desktopと打つと、必ず以下のエラーが表示されます。※実際アプリはなんでもいいです。

　E: ロック /var/lib/dpkg/lock が取得できませんでした - open (11: リソースが一時的に利用できません)
　E: 管理用ディレクトリ (/var/lib/dpkg/) をロックできません。これを使う別のプロセスが動いていませんか?
）
たぶんですが、解消のできない、これに近い状態が発生していたんだと思われます。
またこれは内部的なファイルのロックの状態の話なので、
２番目の最適なダウンロードサーバが見つからない件とは別の話となりますが、いろいろ試してと書かれておられるので、
その最中に２番目の話も解決したんでしょうね。

あまりお役に立てず申し訳ありませんでしたが、
何はともあれ、使えるようになって良かったです。