Baryonyx and Cetiosaurus were to appear in the main series, but they were replaced with Utahraptor and scrapped entirely, respectively.
The Sea Monsters book describes a number of scenes that didn't make it into the series, such as the female nothosaurs leaving their eggs on the beach at night (there is also a picture of Nigel inspecting those eggs, meaning it was filmed) and Nigel meeting the utterly bizarre aquatic ground slothThalassocnus before going to look for the shark C. megalodon.
Originally "Walking With Beasts" was first, but they only recieved money for "A show about dinosaurs", and they made Walking With Dinosaurs.