Originally, Genie's foreman getup was more muscular than in the film.
Iago says the line of "Doesn't get any bigger than that!" No where in the film does he say this.
Footage of Robin Williams is present of him recording "It's a kinder, gentler Genie! Look at this!"
Aladdin is shown with a bloodstain on his left sleeve during clips of the "Welcome to the Forty Thieves" sequence. Originally, there was going to be a bit of blood shown from the Challenge when Sa'luk slashes Aladdin's arm. A dark shadow resembling blood can briefly be seen on Aladdin's arm after he is injured in the final film.
The thieves are shown congregating outside against a dusky background, compared to congregating within the stable.
The same trailer has an instance of Recycled Trailer Music using a snippet of "Jafar's Hour" from the original movie.
Several shots are shown with Genie having the same design as the Aladdin TV series. Dan Castellenata was meant to reprise his role before Disney decided to reach out to Robin Williams again.
Mozenrath was originally planned as the villain in the third film. However, whether he would actually be Aladdin's brother is another story - this is fan speculation, not Word of God.
Sean Connery was originally considered for the voice of Cassim.
The Triumphant Reprise of Arabian Nights at the end of this movie was originally meant for the end of the original film when the Peddler was slated to be the narrator, who would appear at certain points to give the audience the scoop on the story so far through various reprises of Arabian Nights. This reprise, in particular, would've been sung as the Peddler packed up all his stuff, hopped onto his camel and went riding into the night, saying goodbye to the audience to mark the end of the legend.
Dan Castellenata was meant to reprise his role of Genie from the series, but Disney made amends with Robin Williams to reprise his role. This film was Williams' only true reprisal of the Genie character.