This is one of this messages you don't expect, specially when you are trying to restore a backup at 4:00AM in the morning after seeing that the whole farm needs to be rebuilt. The last thing you need at 4:00AM is more problems, just because in four hours the company will start running.
To prevent that I have placed this little post, I hope it will will help.
So why is the "Administration service is stopped. Start the Microsoft SharePoint Foundation Administration 2010 service in order for the operation to continue." is popping up?. Well there is Windows Service called WSSADMIN.exe is used by SharePoint to perform backup/restore operations.
As you probably guessing the service has not been started, so just go to Services in Windows, and find a service called "SharePoint 2010 Administration".
Click on start and voila!