Multiple reasons:
1) The Elites and Brutes have hated each other ever since the Brutes were brought into the Covenant (there's a conversation between a pair of Grunts that mentions the tensions between them, in the Conversations from the Universe booklet thingy (not sure if that's included in the normal edition, i only got the LE)).
2) The Brutes (and Tartarus in particular), are vicious, scheming, power-hungry bastards who are jealous of the Elites' position within the Covenant.
3) The Prophets blamed the Elites for their failure to protect Regret, not to mention the destruction of the Halo in the first game, and so replaced the Elite honour guard with Brutes.
4) The Arbiter learned of the true purpose of the Halos from the Gravemind (i think, or it might have been one of the Monitors), and the Elites didn't appreciate the fact that the Prophets had been lying to them all along about the Great Journey, while the Brutes remained loyal to the Prophets.
As for exactly why the Brutes remained loyal, they presumably still had faith in the Prophets and their Great Journey(they're a new member of the Covenant, so maybe it's the natural zeal of the newly converted), and by usurping the Elites from their position as the most favoured species within the Covenant, believed they would have greater rewards at the end of the Great Journey.