田中です。
堀川様、ご回答ありがとうございました。

念のため、一度DBを削除し、削除が完了したか(=データベース.mdfが存在していないか)をチェックしてからリストアするようにテストもしてみました。
しかし、結果は同様でした。

また、データベースを削除せずにAccessのプロジェクトでデータベースに接続したまま状態でリストアしたり、
use databasename
を実行した後にリストアを行うと、ちゃんとデータベースの使用中エラーが発生したので、
もし、使用中のユーザがいてもエラーが返ってくるものと思われます。
（ちなみに、このプログラムを行うアプリケーションでは起動時にDBの使用チェックを行った後、排他をかけています）

とりあえず、現段階では以下の処理を行うことにより実行可能になっています。

バックアップ：
　バックアップを実行した後、バックアップファイルが正常に作成できているか
　（１秒ごとにバックアップファイルのサイズをチェックして、サイズが前回チェックした大きさと
　　変わっていなければ作成完了と判断）
　をチェックして、作成できていれば次の処理を実行する。

リストア：
　リストアを実行した後、データベースが正常にリストアできたか
　（１秒ごとにリストアしたデータベースに接続を試みて、正常に接続できれば
　　リストア完了と判断。判断後は接続を閉じる。）
　をチェックして、接続できていれば次の処理を実行する。

念のため上記チェックには最大チェック秒数もセットして、最大チェック秒数になっても
作成完了と判断できなければエラーを返すようにしています。

上記方法でとりあえず実行はできる状態にはなったのですが、原因が不明なままなので
すっきりしないのです。

端末毎の仕様に影響するようなロジックは組んでいないと思うのですが、、、、

すみませんが、引き続き、もしかすると、、、という情報がありましたら
ご連絡いただけるとうれしいです。