IMDB says this:
It's a widely reported myth that the original title of the film was "South Park: All Hell Breaks Loose" and the MPAA forced Trey Parker and Matt Stone to change the title, stating that all movie titles must be G-rated (despite the fact that there are many movies with the word "hell" in them - Hellraiser (1987), Hellfighters (1968), From Hell (2001), etc.). The story comes directly from Parker and Stone who claim that they submitted the film with the original title and were forced to change it. Richard Taylor, a spokesman for the MPAA, denies that any film was ever submitted with that title and that the MPAA did not reject the use of the word "hell" in the title.