All-Star Cast: As detailed in Billing Displacement and The Other Marty below.
Billing Displacement: Dolph shows up on the police lineup poster, which is odd because he doesn't even appear until the second half. Especially odd in that he is not played by a name celebrity, and holds a sign displaying "Xzibit as Chief Grizzly." Twitchy also holds a sign advertising Anthony Anderson as Bill Stork, both minor characters but more major than Dolph. Flippers appears but David Ogden Stiers' name does not, and Boingo is completely absent (which probably helps hide the plot twist). Needless to say, it is an odd poster.
In terms of the actual billed cast:
The actors playing the four suspects are credited in this order: Anne Hathaway, Glenn Close, Jim Belushi, and Patrick Warburton. Warburton is easily the film's second most prominent character. It's fairly reasonable that Close is billed ahead of him, but he definitely shouldn't have come after Belushi.
This is followed by the three investigators: Anthony Anderson, David Ogden Stiers, and Xzibit. Stiers and Xzibit are the ones running most the investigation, while Anderson is largely just hanging around. Some trailers even mention Anderson instead of Warburton, while, as mentioned above, some posters and covers don't mention Stiers.
Then we get Chazz Palminteri, who is in the movie for less than a minute, getting billed before Andy Dick. Partially justified by giving Dick the And Starring treatment on some posters, which he doesn't get in the movie proper.
Last on the bill are Cory Edwards and Benjy Gaither, both of whom are complete unknowns. Edwards' character is prominent enough to semi-justify it, but Gaither is a One-Scene Wonder.
Completely Different Title: The French title is La Véritable Histoire du Petit Chaperon rouge, which means "The True Story of the Little Red Riding Hood.
"Be Prepared" is much longer on the soundtrack - with an extra running of the chorus before the bit where Gaither slides down the scale that is not in the final film or the deleted scenes. The deleted scenes version runs an additional eight seconds, with some extra lines added in near the beginning where Japeth steps closer to Red and then eats a rose before the bit where he tips a chair over.
Not exactly cut so much as truncated, but "Great Big World," Red's song, is much longer on the soundtrack - the first verse, the chorus, then a second verse and a refrain of the chorus. In the film, we see all of the first verse (shots of Red riding her bike), but as soon as Red is carried across a stream by hummingbirds, the scene cuts to her on her bike overlooking a valley and the song's refrain. The first run of the chorus and the second verse were animated fully and can be viewed in context on the deleted scenes (the chorus is sung by some beavers riding a log downstream as Red rides on the shore, while Red sings the second verse while she makes deliveries).
Deleted Scenes: The deleted scenes on the DVD release extend several of the songs. You can also listen to the full versions if you buy the soundtrack:
An extra verse in "Great Big World", with shots of Red actually making deliveries (her role as a delivery girl has the feel of an Informed Attribute in the full film because there, we only see shots of Red riding her bike, singing to herself and exchanging greetings with passersby). The verse is spliced in between the shots of Red's bike being carried over the river by the hummingbirds and her coming to a stop at the top of a cliff overlooking a valley.
An additional verse in the "Schnitzel Song". The shot of the kids cheering and throwing their schnitzel sticks into the air doesn't make sense in the final cut. In the deleted scene, they are shown to be throwing them up in ovation to watching Kirk and two children tap-dancing on a stage.
An additional verse to "Tree Critter" prior to the ski race.
The restoration of about five seconds of audio to "Be Prepared", which inserts a shot of Japeth biting down on a tulip after Red says, "That's great, but could you just help me find my Granny's house?" and before the shot of Japeth standing on a chair that tips over. Due to its cutting location, in the final film, Red can be heard speaking although her lips aren't moving for about a second once the music starts. It's still missing a running of the chorus right before the part where Gaither slides down a scale.
Executive Meddling: The Weinstein Bros. had the songs cut down because they felt that audiences would be impatient with them. Anyone who viewed the full songs in the DVD bonus content will strongly disagree:
The second verse of Red's song "Great Big World" and Kirk's "Schnitzel song"
A verse in the song Japeth sings in his shack was cut. The cut was at such a point that Red starts to say something that is cut off when the angle changes.
Red was originally played by Tara Strong, and replaced by Anne Hathaway. Strong remains in the film as Zorra, the fox on Granny's ski team.
Granny was originally played by Sally Struthers, and Chief Grizzly by Joel McCrary, before they were replaced by Glenn Close and Xzibit. Struthers and McCrary receive "special thanks" credits in the film, as this replacement eliminated them from the film entirely.
Voice actor Tom Kenny was originally Woolworth, while Tony Leech, one of the film's three primary creators, was Bill Stork. They were replaced by Chazz Palminteri and Anthony Anderson, but their voices remain in the film as two of the pig cops.
Patrick Warburton as Wolf, Andy Dick as Boingo, and Stiers' performance as Flippers are the only remnants of the original main cast still in the final film, apart from director Cory Edwards as Twitchy and unknown singer Benjy Gaither as Japeth—there was talk of replacing Gaither with a better-known country singer, but this was ultimately cancelled as Gaither embodied the role so well.
Orphaned Reference: The cut first chorus and second verse of "Great Big World" left a couple of these. The line "goodies make the woods go round" comes back when Red says "Woods don't go round by themselves", which just sounds random out of context, and the full line isn't repeated until the Villain Song near the end. The shot of her being carried across the river by a flock of birds is the part of the sequence the Wolf is seen observing during his version of the story, which becomes a rare alternate-angle shot that doesn't match up with anything but at least explains the second Call-Back when Nicky says she was "flying a flock of birds without a permit".