Here is what I've figured out. When you initiate an IDR from a remote server, there is a point where you connect to the Media Server. You supply Server, Domain, User, Password and it creates a Temporary IDR User on the Media Server. You can see this user by clicking on Network, Logon Accounts. This was happening for me. I found a tech article (257160) which outlines how to do a manual restore. So I tried it. Instead of selecting from the media listed by the IDR Wizard, I chose "I will provide my own restore media". The IDR Wizard then waits for you to initiate the restore from the Media Server.
On the Media Server, when you are setting up the restore job, under File Redirection, there is a spot to change the Server Logon Account and the Path Logon Account. The help article (257160) said to change them to the Temporary IDR User mentioned earlier. I did this and the restore worked.
So - the big question is - WHY DOESN'T AN IDR RESTORE THAT IS INITIATED FROM A REMOTE SERVER USE THE LOGON ACCOUNTS THAT IT CREATED IN THE FIRST PLACE? As a remote user you have no control over the login credentials at this point. This seems to be a bug.