If you do a deploy from powershell, do you get any errors?
Nope. deploying and undeploying both seem to go off without a hitch.
When you look at the solutions in central admin, does it show as deployed to the web applications you're going to use it on?
Yes. I've also retracted and redeployed from there and there are no errors.
Do you have multiple SharePoint servers? If so, does central admin show it as deployed to all of the servers.
No, its one server, though there are several sharepoint sites on the one server. They show as deployed to all the servers.
And finally, is the Forms Based Authentication Managenment feature enabled on the site collection?
Yes. I've tried turning it on and off and that didn't make a difference.