結論
時計（システムクロック）が狂っていただけでした。
時計を合わせることで、無事にインストールが進みましたとさ。
問題
初代MacBook Airをcommand+Rで起動し、復元ユーティリティからMac OS X Lionの再インストールを実行したところ「インストールの準備中にエラーが起きました」とエラーメッセージが表示され、先へ進まず。
何度か試すも状況に変化なし。ネットワークには正しく接続されている模様。
突破口
インストール時のメニューに「インストールログ」的なものがあり、それを見てみると証明書関係のエラーが発生している様子。
そこでふと思いつく。「時計が狂っているのでは？」と。
解決
復元ユーティリティからターミナルを起動してdateコマンドを実行。やはり時計の日時が狂っていました。
同じくdateコマンドを用いて時計を合わせると、インストーラが先に進みました。
めでたしめでたし。