Advent Children Complete is like a director's cut of the movie. There were apparently a few things that, due to funding issues, they couldn't do in the movie, or there ended up being things that they wanted to add or change slightly.
It's the same story, but with added scenes that make the movie flow a bit better, and just overall more entertaining. There's like a half hour of extra footage. It's essentially the definitive version of Advent Children, and it's the one that Square really intended for us to see.