Same problem here after changing my SD card. I've tried everything listed here in this thread but it just won't stop displaying the "Failed to Play..." message.
I listen to my music daily on the train but I'm now seriously considering another music player which would be a real shame. I've been a Poweramp user for years but this has made me think about switching... it shouldn't really be that hard!