I bought the game in disc form yesterday (06/March/2016), the latest patch is installed, I’m online, and there are a few missing Skulls.
Halo CEA: Grunt Funeral, Pinata, Bandana, Boom
Halo 2: Grunt Funeral, Pinata, Bandana, Bonded Pair, (uncertain: Boom, Feather)
Primary Account: First launched the game online after updating. Skulls not available.
Junk Account: First launched the game offline before updating. Skulls available. Updated game. Skulls still available. Deleted save file. Skulls no longer available.
So I’m guessing the update has a bug that disables the pre-order Skulls if you install it before your save file is generated.
Solution: delete all save data for everyone, uninstall the game, reinstall, launch the game offline with everyone, update.