First things first, check to make sure you aren't hiding songs behind a filter. The last Rock Band 3 game patch allowed players to hide songs by giving them a 1-Lighter Rating. It is possible to accidentally give a song a 1-lighter rating without realizing it, and if this filter is on then those songs will be completely hidden.
If no songs are being hidden by the filter, then you will need to redownload any songs that you are missing. To re-export Rock Band 1, you'll need the game disc. For every other Rock Band title, including all Rock Band DLC, you can download it from the music store.