I'm the product manager at salesforce.com responsible for profiles and permission sets. Any issues that come up are definitely a concern for my team and me to solve.
John Brock (one of our QE) and I just walked through both a MdAPI deploy using workbench (http://workbench.developerforce.com) as well as a change set deployment.
I was able to deploy both standard and custom object permissions through workbench and standard object permissions through change sets. Both deployments were successful. We don't migrate assignments of permission sets to users in the MdAPI, but just in case, I did make sure we were able to deploy the permission set that was assigned to the Sites user in both the sandbox and production.
Also, we spent a lot of time building validations into org-wide permission sets so if there was an invalid permission set assignment, we typically would fail the deployment with an error message rather than drop the permissions on the floor.
I'd like some more information on the issue you're encountering.
Can you please tell me:
1. are you migrating standard | custom | both standard and custom object permissions
if standard object permissions, which object and what are the permission settings (CRUD) on them
were any of the object permissions on managed package objects (which aren't supported in the MdAPI)
if custom object permissions, did you include the custom object as well in the change set or just the permission set
did you test this only in change sets or did you try either the Force.com IDE or a tool like workbench which supports MdAPI retrieves and deployments?
was the org-wide permission set assigned to the sites user only or other users (with other user licenses) and if so, which licenses
Please let us know more about your use case and we'll see if we can reproduce it. If we can reproduce it, we'll get a fix in there for you.
Sorry you're encountering this!
btw, @jkraybill if you encounter any missing features / bugs / unsupported enhancements, always feel free to reach out as we'd rather find out sooner than later and get it fixed as fast as possible for you. Thanks!