I have a 60GB 5G with every single track on it tagged with album art, and I've had no problems whatsoever. It may be that I add all my album art through iTunes manually. I've found that the automatic art loaders generally leave a lot to be desired.