I had the exact same problem with New Vegas. Everytime I leave Caesar's tent the game slows to a crawl and I can't even turn it off without holding down the power button. Welcome to the wonderful world of unfixable console problems.
I had a similar problem a while back with Red Dead Redemption. The problem turned out that one of the patches/updates was flawed. I had to delete the update and let the game redownload it. This didn't effect the game saves or profiles.
Thanks for the responses. I have already tried to delete all saved data and even pulled out the ethernet connection. The game still freezes at exactly the same point right at the entry to the game after choosing the difficulty level.