I have a 5.5G iPod 80GB and I've tried to add album art (embed) into the mp3 tracks.
I've successfully embedded the art into the tracks, but when I upload them to my iPod the art doesn't show.
I've also tried some test files with the art named 'folder.jpg' to see if that cures it, but it doesn't.
Can you also check Options > Tags > Mpeg if ID3v2.3 utf-16 or ISO-8859-1 is used?
See if switching between those two and saving the tags again with helps.
If not, then this Sharepod program probably has issues or no support for embedded covers.