Check your Filesystem, I had the same problem, tag cache update would go on forever...hours....
On linux i did a (change /dev/sdb1 to your device location)
# fsck.vfat -a /dev/sdb1
dosfsck 2.11, 12 Mar 2005, FAT32, LFN
/Gillian Welch
Start does point to root directory. Deleting dir.
/Crosby, Stills, Nash & Young
Start does point to root directory. Deleting dir.
/Yann Tiersen
Start does point to root directory. Deleting dir.
Reclaimed 384 unused clusters (3145728 bytes) in 1 chain.
Free cluster summary wrong (553925 vs. really 558941)
Auto-correcting.
Performing changes.
/dev/sdb1: 2489 files, 1879547/2438488 clusters
# fsck.vfat -a /dev/sdb1
dosfsck 2.11, 12 Mar 2005, FAT32, LFN
Orphaned long file name part "Gillian Welch"
Auto-deleting.
Orphaned long file name part "Crosby, Stills, Nash & Young"
Auto-deleting.
Orphaned long file name part "Yann Tiersen"
Auto-deleting.
Performing changes.
/dev/sdb1: 2486 files, 1879547/2438488 clusters
and from then on tag cache took a few minutes on about 1500 songs. Funny egnoth i had to run fs-check twice to correct all errors.
Edit: Proper code formatting.