Unfortunately, it looks like the Nokia music player on the N95 doesn't recognize the format of the new iTunes Plus downloads. To get around this, I right-clicked on the files in iTunes and selected "Convert to AAC". The newly converted files could then be transferred to the N95 and worked flawlessly (including Artwork).
[kirkmc adds: Interesting. This suggests that they are not standard AAC files. Can anyone else confirm whether these files work on other AAC-supporting devices? Note that the "Convert to AAC" command, in the Advanced menu, will change the bit rate of the songs, if your iTunes Importing preferences are not set to 256 kpbs. Perhaps the bit rate is causing the problem?]
Mac OS X Hints
http://hints.macworld.com/article.php?story=20070530080720994