I figured this would be as simple as entering the new password, but apparently there is no way to re-enter your password on the phone. The google recommended fix is to delete your google account on the phone (!!!), clear the data from all your apps that use google (!!!), and re-add the account.
I did that, and other than the extreme annoyances of having to re-do all my settings for those apps, my sync settings, etc (all for just a simple password change), the big problem is that now all of my contacts are gone.
I thought I had it set up to sync with my google contacts, but apparently if you add a contact through the contacts/phone app it doesn't do that (???) and re-syncing my google contacts just adds a bunch of email addresses. If I go into my app manager there is an application called "contacts storage" which is 9mb and I'm guessing has all the contact info that was saved to the phone? If so, how do I load this back?