Change the language and location of your Xbox to English and USA, and Halo 3 should work just fine, at least in Sweden. I just tried it. Credits to Snygge Oscar.
Thank you, it worked!
(I live in Sweden)
It seems like only people in northern Europe have this problem…
You can change it to UK aswell.