When doing a redesign, we always recomend that clients sustain as much of the internal links as possible. They don't have to be in the same place on the page, or look the same way, but as long as the links are preserved somewhere on the page, you are least likely to see a ranking/traffic decline as a result of a redesign. However there are many other aspects to a sites on page infrastructure that also need to be preserved during a redesign. Some of them include: URL structures, text based content on the page, and title tags. Good luck!
Statements made by me in these forums do not reflect the thoughts or opinions of my employer.