An "undo" feature would also be incredibly useful.

Hugo and I were talking about this in the car a couple of weeks ago -- when I accidentally nuked his playlist by pressing Down one too many times.

Essentially, we thought that it'd be really easy to store the current running order in a reserved bookmark slot (not necessarily persisted), so that you could undo mistakes fairly easily.