Itunes keeps a database of album art that it syncs with the IPod. If you add album art/lyrics/tags to the files with another program after these files are imported into itunes, then Itunes does not know about the change and therefore dues not update the database.
Try deleting these files from ITunes (not the computer, of course) and re-importing them after the changes are done. (ITunes does let you drag and drop the files. If you don’t delete the original, you’ll end up with duplicates … one with and one without the changes, as itunes sees it as adding to the database not updating.
Additionally, when adding album art, make sure you have the “Save Cover for IPod” checked in the program Options (Tools> Options> General Preferences).