I had a similar circumstance a few days ago, wii was version 3.3 and had had wii fit update applied.
after playing about with multi-cios and testing sam & max using the original patch ios33 idea, when wii-fit was inserted it asked to apply its update again.
i can only take a guess that you may have been installing / changing cios recently? and that when you are inserting brawl it doesnt find something quite right with an ios that is installed.