I have had slow loading on my iPod nano 5G, too. However, it only does this when it has 2GB or less free. I have a 16GB nano. So up until the last 2GB it loads about a song every second or slightly faster. Then it hits that slow point and takes about a minute per song. I took it to an Apple store to have a Genius look at it, but they didn't do anything useful other than say, "It could get slow as it gets closer to full." We tried a few restores, but that didn't help at all.
I do have 3 other identical nanos I can try when I get a chance, so I'll see if they all have the same problem.