iTunes has been around for a long time and has some odd idiosyncrasies, so it's not surprising that sometimes one's iTunes library needs a serious "teardown and rebuild" in order to resolve problems encountered while using iTunes or with 3rd party software that works with it. If your library is many years old or you use an unusual configuration, the below is especially likely to help resolve issues. If you're not able to keep all of your media in one folder on a single volume, stop reading because the below requires this.
First, I'd recommend something less traumatic:
Reorganization of your iTunes library. In iTunes Preferences "Advanced" section, turn on "Keep iTunes Media folder organized" and "Copy files to iTunes Media folder when adding to library" if they are not already on. From the main menu in iTunes, File > Library > Organize Library... > turn on "Consolidate files" (and "Reorganize files..." if it is available), then click OK.
If reorganization did not resolve your problem(s), you may want to take extreme measures: A vigorous rebuild of your iTunes library. This method will cause you to lose your star ratings and play counts, and naturally will change the "date added" of all tracks -- so this isn't for everyone.
A. If you have room somewhere, make a back up copy of your music library just in case something goes wrong. I can't guarantee that these steps will all work properly for you, but they have for me in the past. If you have a big library, remember that a new external hard disk is pretty cheap.
B. In iTunes, choose File > Library > Export Library and save it somewhere you'll remember it, like your Desktop.
C. Click the "Music" section in the left, select all tracks in your library, and press the delete key. Do not delete the files themselves when iTunes asks! Be certain that you "Keep Files"!
D. Quit out of iTunes.
E. In Finder, navigate to your iTunes folder (normally within home/Music/) and move all of the iTunes Library... files (i.e. "iTunes Library", "iTunes Library.itl", "iTunes Music Library.xml", "iTunes Library.xml", whichever ones you have) files somewhere safe. If nothing goes wrong, you'll be trashing these afterward.
F. Launch iTunes and you'll see that your library has been reset clean and clear. Don't panic. In iTunes preferences Advanced section, ensure "Keep iTunes Media folder organized" and "Copy files to iTunes Media folder when adding to library" checkboxes are on. If you intend to keep your music elsewhere than your home folder, also change your "iTunes Media folder location" here.
G. File > Add to Library, and choose the top-level folder containing your music files. It may take a long time to import everything. If you have music in multiple locations, you would need to do this step for every location containing music files.
H. When finished, File > Library > Import Playlist... and select the xml file that you created in step B. You will end up with some built-in playlists (like Genius) and smart playlists added as duplicate regular user playlists that you'll later want to remove.
That's it, see if your problems are gone! If so, you can delete the files you created in steps B and E. If your problems still exist, you may want to take the files from step E and drop them back into your iTunes folder (after quitting iTunes, naturally) to "undo" the loss of your star ratings, etc.