I might have an answer. Select each problem track in turn and click the info tab. Make sure the location/name of the physical track matches the name of the track in RB. Sometimes there's a mismatch which can happen when you have relocated a file for whatever reason. Happen to me the other day when I tried to relocate a few tracks I'd moved and although not exactly the same error I was informed the track was already in the database when I knew it wasn't. Eventually I realized that I'd screwed up early and relocated a RB track to the wrong physical mp3.
Depending on the amount of tracks in your RB then the other way is to show the location column and then sort it alphabetically and see if any duplicates jump out at ya.