A couple of things I noticed in my situation.
1. It works perfectly offline, no freezing at all. Just go to Settings -> Network -> Go offline to test
2. Even with a wipe of saved data it freezes. That is with a fresh character and no worlds. I used two different methods to test this. First was I booted the game up on my brothers console, downloaded save, then wiped it from his console and the cloud (the save was still on my console). The other was to delete local save on my own console and cancelling the synchronization. In both situations I had no prior saves, obviously.
To me it appears that there is something tied to the gamertag itself that causes the issue. What I can think of is that there is something on Microsoft's end (probably an error with the cloud - seeing as my error first occured during the cloud outage).
I can actually join other friends' games in progress if I go to their profile and select "Join game", but all my stuff is in my own world, and at this point (70-80 hours in) I really don't want to start all over.
I've tried to reach Xbox support and 505 Games through twitter, but so far no response.