Technically, everybody takes a singular verb. Try replacing it with "every single body" or "every person".

The main ambiquity in the phrase is that 'their' isn't -technically- correct as a gender neutral third person possessive pronoun, despite its common usage in that form. (Say -that- five times fast!) If you replace 'their' with 'his or her', the agreement makes much more sense:

    Everybody changed his or her mind.

Personally, I would just rewrite it completely:

    They all changed their minds.

English is fun!