I added a solution successfully through the stsadm command. But then when I tried to deploy it, it was stuck in a "Deploying" state. If you have a multiple WFEs and have a WSP that is stuck in a Deploying state, the job may be stuck in queue on the front end you are depoloying the solution from or may be stuck on the other front ends.
Execute this command for all servers:
stsadm -o execadmsvcjobs
This will execute the pending jobs on the particular server the command is being run on.