this is a pain but this is what you must do.. sometimes i've even had weird things happen (i think i had napster then) my files didn't like their database.. they forced me to redownload everything.
you cant just redownload the files your having trouble uploading to your droid.. i think the easiest way is to do a cache wipe. this will delete all your downloaded songs. as soon as you do that.. go in to skype and download like 50 playlist whatever you need.. then you should be clean.
if you need to know how to delete you cache. you can't do it from settings i just read about it.. its a poorly engineering settings config. read this: