Firstly - which revision of Rockbox are you using?
Secondly - Are you using the build for the 80/60GB Video, or the 30GB Video (it may be worth changing to use the 30GB one if you're currently using the 80/60GB one).
Thirdly - Are you using the database or the filebrowser ?
Fourthly - How are you adding the songs to the playlist? Singly, or in groups ?