Tips for re-designing a traditional newspaper?

I am working with a few friends to re-design the entire layout and content for a small town newspaper. Unfortunately it is still going to be in black and white (but we will have two color pages in the next issue). The paper has used the same layout,logo and template for the past 15 years. So any tips, ideas for re-designing a fresh look would be welcome. Also if you could point me towards some useful resources on the web that would be amazing