I was going to put this in its own thread in the Verizon GNex forum, but I worked out a simple fix based upon what the XDA guys discovered, at least for the Facebook app on 4.0.4.
Instead of signing into the Facebook app with your GMail address, use the email address Facebook gives you. You can find out what it is in your account settings in Facebook, but it should be your first and last name and "@facebook.com", so it will look like "johnsmith@facebook.com". Note that you don't need to make this your default email address in Facebook, i.e., don't change any settings for your Facebook account, just find out what your @facebook.com email address is.
Once you have it, on your phone, go to Settings--Accounts--Facebook and remove your Facebook account (there will be a menu button in the top right corner of the screen that will give you this option). Don't delete the app itself. Once you remove the account, exit settings and launch the Facebook app. It should ask you to sign in. Instead of your GMail address, enter the Facebook email address described above as your account name. Enter your password as normal and the app should sync your account again. Uploads to Picasa from the gallery app should now work. Note that it may prompt you for permissions when you upload a photo and you must accept them. This little trick even solved some general wonkiness I've been having with the gallery app.
The problem appears to stem from syncing accounts to the phone that use your GMail address as the account name (besides your Google account itself, that is). So, if you use your GMail address to sign into an account you need to sync to the phone, try to find an alternate way of credentialling the account, one that doesn't use your GMail address as the account name. I only needed to do this for Facebook. I did not try it with other services.
Did this work for you?
Facebook
Twitter
Instagram