I deleted a playlist off my phone to make room for some video I was going to take and now after I synced my phone again, it deleted the playlist off iTunes? How can I get it back? I've tried restoring the iTunes.xml trick and no dice.

Any help appreciated.