i was facing a similar error few days ago. Nothing was working. Finally i had to delete the solution from PowerShell and then re-deployed. it worked then.I used following command on PS. don't know if that works for you. (Get-SPSolution solutionName.wsp).Delete()