Error occurred in deployment step 'Retract Solution': The language-neutral solution package was not found.
Hi, Re-opening VS didn't help, here is what did the magic for me.
From Powershell, delete the solution and redeploy using VS fixed for me.
(Get-SPSolution solutionname.wsp).Delete(). Solutionname.wsp is the name of the solution that is causing deployment failure.