The brotherhood of Makuta was a thing established atleast as early as 2005, if not 2004. (Which funnily enough lead to speculation that 'Makuta' was,not only a species, but also the name of the species, as would be revealed in 2008.) The brotherhood was mentioned by name in a series of BZPower posts called "BIONICLE Myths and Misconceptions" which was written in 2005-2006 by a fan, debunking way old misconceptions like Toa turning back into Matoran. So, it was established in canon by the time of 2005, and presumably by the story team, in 2004 atleast.
But of course; That doesn't mean that the brotherhood was originally intended to be composed of Makuta, nor that it was part of the original story bible, which it probably wasn't at all.