Sharepoint - Solution "Not deployed" yet actions are successful

SharePoint's solution deployment is a bit of a black box. I would try two things:

1) Use -Force on the Install-SPSolution cmdlet to instruct SharePoint to override files, etc., and hopefully result in "Deployed".

2) If #1 doesn't work, I would retract and remove the solution. Then restart the SPAdminV4 and SPTimerV4 Windows Services. Then re-add the solution and use Install-SPSolution with the -Force parameter.