If I added directory to a playlist, will I be able to delete individual song (which is in this directory) via long-press menu when in playing mode? I think no.
We will need to store list of songs in playlist in some sort of database in order to not walk the directories at every startup. I think we could store that lists together with some metainfo (song length, mp3 tags, ...) in sqlite database. But the question is when to update this db? I'm sure that updating is going to be very expensive operation. So, is it ok to update song list only by user's request?
How directory selector should look like? You're saying about list with checkboxes, does it means that you will need to mark all directories for the current playlist at one dialog? This would require some kind of tree-view which is not a good idea for thumb-oriented ui. I think it will be more convenient to add one directory at a time with the dialog that will display directory contents in a list (going into subdirectory when tapping on it)