It tells you which catalogs you're missing. If you're on Xbox, which you seem to be, the catalogs will show you that you already downloaded them if you ever have before on any Xbox. Just download them again to be sure.
Doing something wrong then. I ran into the same thing but was able to download the necessary packs and play. Make sure you don't have any incomplete downloads in the game folder on your HDD. Or make sure you don't have them in multiple locations like flash memory and the HDD or something.