You can highlight the top with one finger and the bottom (of that screen) with different finger and it will highlight all between. Then you can delete all on that screen. Not as cumbersome as one by one...
RIM really need to fix this for the new OS, The only way in clearing it all up at the moment is to goto Message then hit the menu key. and goto [View Folder] and scroll to call logs. open it and use the delete prior option.