That was it.
The $live_site variable in configuration.php
Sometimes you might be getting URL errors. For example, the first page might display but clicking on any link returns a 404 error, while some other times the first page displays very weird, like the CSS and images are not loading. Both of those issues have nothing to do with the restoration itself, but your server setup and a clash with how Joomla! works. The easiest way to work around it is using the $live_site variable in your configuration.php file, if you haven't already set it up in ABI's Site Setup page. Edit the configuration.php file in the root of your site and modify it so that the line starting with var $live_site looks like this:
var $live_site = "http://www.mysite.com";
or (if you have installed in a subdirectory):
var $live_site = "http://www.mysite.com/mypath";
This will let Joomla! figure out the correct URLs to your site's CSS files, images and links and these errors will go away.
If you restored to a server which required the $live_site hack, next time do yourself a favour: use ABI's feature for changing the $live_site variable. It is available in the second to last step of the restoration procedure, just under the text boxes where you define your site's name and email details.