同様の症状に見舞われました。
・コピー先のHDDをフォーマットしたり
・レジストリのWindows Backupをクリアしたり
・タスクスケジューラのWindows Backupをクリアしたり
いろいろ試したところ、開始直後に 0x80070002 エラーが出るようになりました。
最終的に決め手になったのは、Windows Backup のsdclt.exe をコマンドラインから叩くことでした。元記事はUS版のMicrosoftフォーラムです。
http://social.technet.microsoft.com/Forums/en-IE/windowsbackup/thread/30b0857c-3a08-4575-9625-311f967dfa14
sdclt /DELETECATALOGANDKICKOFFNEW を実行すると、バックアップが走り始めたみたいです?
試してみてください。