I am completely unable to find a game in matchmaking after the latest patch. The search will restart several times before the game crashes and sends me back to the dashboard. The search times before the patch were not much better. The search averaged 10-15 minutes which is completely unacceptable.
Quit and restart game or possibly power cycle console. Not ideal but it helps. I had the same thing. After the patch it was better. I think auto resume messes stuff off. You have to quit out of MCC after every time you are done playing. When I come back in after quitting, it loads much faster again.
This should not be a needed step every time you play IMHO, but if you want the optimal (non-optimal) experience for now, heed this advice.