Well we know the World Eaters and Dark Angels only changed their names not their colours so I presume most of the other Legions were the same.
We have several changes:
War Hounds to World Eaters:
Imperial Heralds to Word Bearers. Name change after they found their primarch, colour scheme after Dropsite massacre
Luna Wolves to Sons of Horus
Dusk Raiders to Death Guard (other way around in this picuture, left is Death Guard, right is Dusk Raiders)
Everything below didn't change colours but had different names before finding their primarch:
Dragon Warriors to Salamanders
Angels of Death to Dark Angels (according to Angels of Caliban book)
Storm Walkers to Iron Hands
Alpha Legion is noted as having 730+ different names before their official one
Iron Warriors unofficial cognomen: Corpse Grinders
Raven Guard unofficial cognomen: Pale Nomands/Dust Clad
Info above comes from the different FW Campaign books (Except the Salamanders and Dark Angels ones who come from Lexicanum and Angels of Caliban).
Edit: well seems the forum screwed a bit with the img sizes, or I derped. Sorry about that!