I was getting this error when trying to import a solution into an On Premise Dynamics 365 environment.
This was a solution that I knew had previously imported into other environments, so I was very confused why it would not import. Turns out, the Sandbox Processing Service on the server was not actually running.
Restarting the Service allowed the solution import to proceed.
I believe this must have happened as we had experienced a power cut, and I have certainly seen Dynamics services not restart properly when a server is not safely switched off correctly. Also, it may have had something to do with the fact that this one little Virtual Machine server was running about 20 different CRM Organisations at once.
Anyway, never assume that its an issue with your solution. Nine times out of ten, it is, but always remember to check your environment as well.