I found out how to fix it. It's in the Control Panel->User Accounts->Manage Your Credentials

One of the things in the "Vault" was the user it was picking for deployment. Deleting that user allowed me to click "Deploy" in BIDS and have it ask for the login again. Then I could enter a login which works.