If you've come across this error when trying to import a solution into an environment and wondered what's going on, or how to find out more information?

If you want to 'try again later' and use this time to practice some self-care, then go ahead. If you want to fix it and get on with work - read on.
Troubleshooting
As with most things, using the browser's development tools is indispensable, check the console log or network tab for errors, and this is what you'll find.
Failed to load resource: the server responded with a status of 404 ()
And perhaps...
GET https://unitedstates.api.powerapps.com/providers/Microsoft.PowerApps/apis/CONNECTION-REFERENCE-NAME-00000000-0000-0000-0000-000000000000?api-version=2016-11-01&%24filter=environment eq '00000000-0000-0000-0000-000000000000' 404 (Not Found)
Or if you have "Log XMLHttpRequest" enabled you'll also see this slight variation on the above...
Fetch failed loading: GET "https://unitedstates.api.powerapps.com/providers/Microsoft.PowerApps/apis/CONNECTION-REFERENCE-NAME-00000000-0000-0000-0000-000000000000?api-version=2016-11-01&%24filter=environment eq '00000000-0000-0000-0000-000000000000'".
It also might show in the console log with '...' in the middle of the URL, hiding the most useful part.
What's going on?
It's all about sequencing... What's happening is the import process is trying to create the connection reference, but since the connector doesn't exist yet, it can't do it.
The Solution (pun intended)
To fix this, simply stick the custom connector in a solution of it's own, literally just the one object in it. And then import that into the destination environment first.
If you ask me, it's honestly lazy on Microsoft's part, surely they could prioritise the import of Custom Connectors before any Connection References in the same solution, but at least it's a simple fix for us.
It's actually mentioned on the Microsoft Learn article about "Use a connection reference in a solution with Microsoft Dataverse"
It's the 2nd item under 'Known Limitations'...

So, go ahead and do that, and once you see "Solution "MY CUSTOM CONNECTOR SOLUTION" imported successfully."
, you can then try to re-import the original solution.
And yes, you can leave the Custom Connector in that solution, to streamline future updates in one place. It's just the initial import and creation process that's fubar.
And here we go!

Job done.
Another one for THE BOOK.